[C++, 코딩테스트] Softeer : 수퍼바이러스 with 분할정복

문제를 풀기 전에 분할 정복에 대해서 알아보자.

 

분할 정복이란, 문제를 풀 때, 비슷한 부분의 작은 부분으로 쪼개서 계산하고 그 결과들을 통해서 답을 도출하는 방법이다.

총 3가지 단계로 나눠서 문제를 풀게 되는데,

 

1. Divide : 기존 문제를 작은 부분 문제들로 나눈다.

 

2. Conquer : 각 부분 문제들을 해결

 

3. Combine : 부분 문제들의 솔루션을 통해서 기존 문제를 해결

 

이런 식으로 문제를 푼다. 분할정복의 대표적인 예로는 병합 정렬이 있다.

 

수퍼 바이러스 문제는 계산하면서 수가 너무 커지기 때문에 미리 계산을 해서 그나마 작은 수들로 계산을 해나가야 하기 때문에 분할 정복을 사용해야한다.

 

 

 

 

 

여기서 1000000007의 정체를 궁금해 하는 사람이 있을 것이다. 1000000007는 10억을 넘는 수 중에서 가장 작은 소수라고 한다. 그래서 1000000007로 나눌 경우에는 10억보다 큰 수 인 경우에는 10억보다 큰 부분은 잘려나가고 10억보다 작은 부분만 살려낼 수 있는 것이다. 수가 너무 커지고 어차피 우리가 원하는 정답은 1000000007로 나눈 나머지의 값이니까 곱셈을 하는 과정에서 1000000007을 넘어가는 수는 버리고 계산을 이어가도 답을 얻는데 지장이 없다. 예를 들어서 나는 5의 3제곱한 값의 일의 자리만 원하는데 5 * 5 * 5 = 125의 일의 자리인 5를 가져오든 5 * 5 = 25에서 5만 가져와서 5를 다시 곱한 25에서 일의 자리의 5를 가져오든 결과는 똑같다는 뜻이다.

 

#include<iostream>
#include<cmath>

#define mod 1000000007

using namespace std;
long long K, P, N;

long long calc(long long count){
    if (count == 1)
        return P;
    long long result = calc(count / 2);
    result = (result * result) % mod;
    if (count % 2 == 1)
        result = (result * P) % mod;
    return result; 
}

int main(int argc, char** argv)
{
    cin >> K >> P >> N;
    cout << (calc(N * 10) * K) % mod;
    return 0;
}

 

 

사실 이 문제는 변수의 크기 제한이 없는 경우에는 K * P^(10 * N)을 하면 간단히 끝나는 문제이다. 하지만 우리가 계산할 수 있는 가장 큰 타입은 long long이고 long long의 범위는 -9,223,372,036,854,775,808부터 9,223,372,036,854,775,807까지이다.

 

즉 P의 최대값이 10^8인데 P를 세제곱하면 바로 오버플로우가 발생하는 것이다. 따라서 곱을 할 때마다 100000007로 나눠주어야한다는 것이다. 이게 첫번째 포인트이고 두번째 포인트는 만약 완전 탐색으로 이 문제를 풀려고 한다면 N번의 곱셈을 해야할텐데 그럴 경우에는 N의 최대값이 10^16이기 때문에 1초 제약(1억회 시간복잡도)을 넘어가게 된다. 따라서 분할 정복으로 이 문제를 풀어야하는 이유이다. 

 

위 공식처럼 재귀를 통해서 절반씩 잘라가며 값을 구하고 그 값에 값을 곱하면서 곱셈 횟수를 logN으로 줄일 수 있었다. 

 

 

문제가 처음에는 이해하기 힘들고 다른 사람의 문제를 보고야 풀 수 있었지만 c++와 알고리즘을 공부하기에는 아주 좋은 문제였다.