[C++]1629번 : 곱셈

문제 : https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

이 문제의 로직 자체는 매우 간단한 반복 연산이지만, 단순히 for문을 사용해 해결하려고 하면 최대 21억 회의 반복이 필요해 시간 초과를 유의해야 하는 문제이다.

 

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long a, b, c;
    cin >> a >> b >> c;
    for(int x = 0; x < b-1; x++){
        a = (a*a)%c;
    }
    cout << a%c << endl;
}

처음에 b의 범위를 제대로 보지 않고 단순히 나머지 값의 크기를 매번 줄어주는 데만 급급해 시간초과가 발생했다.

해당 방식으로 문제를 해결하면 시간복잡도는 O(b)인데 b의 크기가 최대 21억이므로 당연한 결과이다.

 

같은 수를 여러 번 곱하는 거듭제곱 문제에서 유명한 해결 방법이 존재한다. 바로 제곱을 반복하는 것인데, 다음과 같다.

예를 들어 2^16을 계산해야 한다고 가정하자. 2^16은 2^8의 제곱과 같다. 2^8은 역시 2^4의 제곱과 같다. 이렇게 수를 제곱해 가며 계산하면 시간복잡도는 O(log2(n))으로 극단적으로 줄어들게 된다.

해당 로직을 코드로 구현하면 다음과 같다.

#include <bits/stdc++.h>

using namespace std;
long long cal(long long a, long long b, long long c){
    if(b == 1) return a;
    long long x = cal(a, b/2, c);
    if(b%2==0) return (x*x)%c;
    else return (x * cal(a, b/2+1, c))%c;
}

int main()
{
    long long a, b, c;
    cin >> a >> b >> c;
    cout << cal(a, b, c)%c;
}

재귀함수를 사용해 알고리즘을 구현하였다. 곱해야 하는 횟수를 계속 반으로 줄여 가며 값을 구했고, 만약 지수가 홀수일 경우 a^b/2 * a^(b/2+1)로 계산하였다. 같은 계산을 여러 번 하지 않기 위해 계산한 값을 x에 저장한 뒤 사용했다.

추가적으로 main함수의 마지막 줄 %c에 유의해야 한다. b가 1인 경우, 재귀를 하지 않기 때문에 b==1일 때 나머지 연산을 해 주거나 연산을 모두 마친 뒤 나머지 연산을 해 주어야 한다.