[C++] 백준 1629번: 곱셈 (분할 정복)

1629번: 곱셈

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

A의 B제곱을 C로 나눈 나머지를 구하여라.

---

시간복잡도 어림하기

단순 연산 알고리즘

 A의 B제곱을 그대로 계산하고 C로 나누는 연산으로 문제를 해결할 수 있을까요? A와 B의 최댓값은 대략 20억 이므로 20억의 20억 제곱은 계산할 수 없을 정도로 큰 수입니다.

 A를 곱할 때마다 C로 나눈 나머지를 취하는 연산을 어떨까요? 이 방식은 충분히 계산할 수 있을 정도의 수만 나올지는 몰

라도 결국 연산을 B번 반복해야하기 때문에 제한시간 내에 문제를 해결하기 어렵습니다.

 

분할 정복 알고리즘

 A의 B제곱은 지수법칙을 사용하여 그보다 낮은 차수의 곱으로 나타낼 수 있습니다. 예를 들면 다음과 같습니다.

10^100 = 10^50 x 10^50
10^50 = 10^25 x 10^25
10^25 = 10 x 10^24 = 10 x 10^12 x 10^12
10^12 = 10^6 x 10^6
10^6 = 10^3 x 10^3
10^3 = 10 x 10^2 = 10 x 10 x 10

이처럼 지수를 반씩 줄여나가면서 연산을 분할하고 다시 합하는 방식으로 원하는 값을 계산할 수 있습니다.

 

 이와 같은 방식은 몇 번의 연산을 진행할까요? 우선 지수는 반씩 줄어드므로 밑이 2인 log 번 줄어들 것입니다. 문제에서 B의 최댓값은 대략 2^32이므로 계산하는 지수값은 최대 32번입니다. 이를 트리라고 생각하면 트리의 최대 높이가 32인 것을 의미합니다.

 하지만 각 연산을 2번씩 진행해야하므로, 각 노드는 2개의 자식을 같습니다.  따라서 최대 연산횟수는 2^32번이고, 이는 제한 시간내에 문제를 해결하기 어려운 수치입니다. 

 

 그렇다면 어떻게 문제를 해결할 수 있을까요? 각 지수별로 dp에 메모이제이션을 통해 연산횟수를 32번으로 줄일 수 있지만, 조금 더 단순한 형태로 현재 지수의 반의 값을 미리 구해 변수에 저장하고, 이 변수를 두 번 곱해 불필요한 재귀호출을 줄일 수 있습니다. 

---

알고리즘 설계하기

 알고리즘은 기본적으로 위에서 살펴본 분할정복 알고리즘을 따라갑니다. 형태는 다음과 같습니다.

long long solve(int 현재 지수){
    if(현재 지수 == 1) return A;
    
    long long ret = solve(현재지수 / 2);
    if(현재 지수가 홀수라면)
    	return A * ret * ret;
    else
    	return ret * ret;
}

 

 여기서 나머지 연산 로직만 추가하면 문제를 해결할 수 있습니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
using namespace std;

typedef long long ll;

int a, b, c;
ll solve(int e){
    if(e == 1) return a % c;
    
    ll ret = solve(e / 2);
    if(e % 2){ //현재 지수가 홀수
        return (a * ((ret * ret) %c)) %c;    
    } 
    return (ret * ret) % c; //현재 지수가 짝수

}

int main(){
    cin >> a >> b >> c;
    cout << solve(b);
    return 0;
}

 코드에서 새로 추가된 부분은 나머지 연산입니다. 자세한 내용은 모듈러 연산에 대해 찾아보시면 좋을 것 같습니다.

---