[백준/C++] 14731번: 謎紛芥索紀 (Large)(S2)

 

문제

https://www.acmicpc.net/problem/14731

14731번: 謎紛芥索紀 (Large)

 

 

사용한 알고리즘

• 2022.02.02 - [PS/Algorithm] - [알고리즘 개념정리] 7. 이분탐색/분할정복
• 비트마스킹

 

 

풀이

2일 전에 분할 정복을 이용한 거듭제곱으로 풀어서 맞왜틀하다가 던졌던 문제다.
어제 신촌캠프에서 비트마스킹을 배워서 그걸로 다시 풀어봤..다가 맞왜틀한 문제다.

결국 둘 다 AC를 받아냈는데

첫번째 풀이는 
WA : ans += (((c*k)%m) *pow(k-1))%m;
AC : ans  = (ans + ((c*k)%m) * pow(k-1))%m; 
%m가 꼼꼼히 되지않은 것 때문이었고,

두번째 풀이는 
WA : long long ans; 
AC : long long ans =0;
지역변수로 선언해놓고 초기화 안해준 것 때문이었다 ;;

 

소스코드

첫번째 풀이(분할 정복을 이용한 거듭제곱)

#include <iostream>
using namespace std;
typedef long long ll;

ll m=1e9+7,ans;
ll pow(ll b){
    if(b==0) return 1;
    if(b%2==1) return (pow(b-1)*2) %m;

    ll half=pow(b/2);
    return (half*half)%m;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); 

    ll n,c,k; cin>>n;
    while(n--){
        cin>>c>>k;
        ans = (ans + ((c*k)%m) * pow(k-1))%m; //★
    }
    cout<<ans;
    return 0;
}

 

두번째 풀이(비트마스킹)

#include <iostream>
using namespace std;
typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    ll n, c, k, ans=0, mod=1e9+7; //★
    cin>>n;

    for(int i=0; i<n; i++){
        cin>>c >>k;
        // ans += c*k*(2^(k-1)) 를 하기위해 2^(k-1)를 구해보자

        ll res=1, a=2, b=k-1; // a^b를 구해야 하는 상황 (결과값은 res에 담기)
        /* b가 5일때 (예시)
            5는 2진수로 101이고 우리가 구하는 것은
            2^4*1 * 2^2*0 * 2^1*1 임.
        */
        while(b){
            if(b & 1) res = (res * a) % mod;
            a = (a * a) % mod, b/=2;
        }
        ans =  (ans + ((c * k)% mod) * res) % mod;
    }
    cout<<ans;
    return 0;
}