[C++] 백준 1629: 곱셈

문제 이해

- 자연수 A를 B번 곱한 수를 구하려고 한다.

- 단 매우 커질 수 있으므로 C로 나눠주도록 하자.

 

<조건>

- 시간 제한: 0.5초

- 메모리 제한: 128MB

 

<입력>

- A: 곱하는 수

- B: 곱하는 횟수

- C: 나누는 수

A, B, C 모두 (1 ~ 2,147,483,647) 사이의 정수로 int형으로 표현할 수 있다.

 

<출력>

- A를 B번 곱한 수를 C로 나눈 나머지를 출력하자.

 

 

---

문제 풀이

처음에 가장 먼저 생각한건 역시 브루트포스다

A를 그냥 B번 곱해주는 것이다.

 

그런데, B의 최댓값은 2,147,483,647로 대략 10^9를 넘는다.

즉, O(N)의 시간복잡도를 가져도 시간 초과로 AC를 받을 수 없을 것이다.

 

도저히 시간 복잡도를 줄일 방법이 생각나지 않아서 인터넷을 참고했다.

 

 

 

 

이 문제를 푸는 방법은 '분할 정복을 통한 거듭제곱'이었다.

이 방법의 경우 시간복잡도가 O(logN)으로 줄어들어 AC를 받을 수 있다.

생소한 유형이라서 문제를 풀어보지 않았다면 전혀 몰랐을 것이다.

 

 

먼저 사용하는 공식은

거듭 제곱과 관련된 공식이다.

a^b = a^(b/2) * a^(b/2) //b가 짝수일 때
a^b = a^(b/2) * a^(b/2) * a //b가 홀수일 때

b가 홀수인 경우 2로 정확히 나눠떨어지지 않으므로 a를 한 번 더 곱해주는 것이다.

 

 

 

그 후 이걸 분할 정복으로 구현한다.

여기서 주의할 점이 두 가지 있는데,

1. 자료형을 long long으로 할 것.

2. return문에서 재귀 호출을 하지 말 것.

 

이 두 가지이다.

 

 

먼저 자료형을 long long으로 하는 건

a의 최댓값이 int형이 표현할 수 있는 최댓값이고, 이를 한 번만 더 곱해도 오버플로우가 날 수밖에 없다.

그러므로 a를 한 번 더 곱해도 오버플로우를 방지할 수 있는 long long으로 해주는 것이다.

 

 

두 번째, 재귀 호출을 return문에서 하지 말라는 건,

미리 재귀 호출을 한 값을 사용하라는 것이다.

 

만약에 return문에서 사용한다면 재귀 호출 횟수가 재귀 한 사이클마다 4번씩 곱해질 것이다.

이 경우 시간초과가 나기 때문에 이런 테크닉도 중요하다.

 

 

---

전체 코드

#include <iostream>
using namespace std;

long long a, b, c;

long long solve(int b){
    if(b == 0) return 1;
    if(b == 1) return a % c;
    
    long long k = solve(b / 2) % c;
    if(b % 2 == 0) return k * k % c;
    else return k * k % c * a % c;
}

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

    cin>>a>>b>>c;
    cout<<solve(b);

    return 0;
}

 

 

 

---

배운 점

분할 정복을 이용한 거듭제곱이라는 새로운 유형에 대해 배울 수 있었다!

앞으로 기억해서 비슷한 유형의 문제를 풀어내도록 하자.