이번에는 백준 1629번 곱셈 문제를 풀어보았습니다.
이 문제는 A를 B번 곱한 뒤 C로 나눈 나머지를 구하는 문제입니다.
처음에는 단순 반복문으로 접근했지만, B가 매우 클 수 있기 때문에 시간 초과가 발생했고, 이후 분할 정복을 사용해 시간 복잡도를 줄이는 방식으로 정리하게 되었습니다.
문제 설명
자연수 A를 B번 곱한 수를 알고 싶습니다.
다만 결과가 매우 커질 수 있으므로, 실제 값 전체를 구하는 것이 아니라 C로 나눈 나머지를 출력해야 합니다.
즉, 구해야 하는 값은 다음과 같습니다.
A^B % C입력으로 주어지는 A, B, C는 모두 매우 클 수 있기 때문에, 단순 계산으로는 해결하기 어렵습니다.
처음 생각한 방식
처음에는 그냥 A를 B번 반복해서 곱하면서 중간중간 C로 나눈 나머지를 유지하는 방식으로 구현했습니다.
이때 사용한 개념은 다음과 같습니다.
(a * b) % c = (a % c) * (b % c)즉, 곱셈을 할 때마다 나머지를 유지해도 최종 결과는 같다는 점을 이용한 것입니다.
실패한 코드
#include <bits/stdc++.h>
using namespace std;
int a, b, c;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b >> c;
int ret = a;
for (int i = 1; i < b; i++) {
ret %= c;
ret *= a;
}
ret %= c;
cout << ret << "\n";
}이 방식은 로직 자체는 단순하지만, 반복문이 B번 가까이 돌게 됩니다.
즉, 시간 복잡도가 O(B) 가 되기 때문에 B가 매우 큰 경우에는 시간 초과가 발생합니다.
왜 시간 초과가 나는가
이 문제에서는 B가 매우 큰 자연수일 수 있습니다.
그런데 위 방식은 거듭제곱을 직접 하나씩 계산하므로, B가 커질수록 반복 횟수도 그대로 커집니다.
결국 이 문제에서는 단순 반복이 아니라,
거듭제곱 자체를 더 빠르게 구하는 방식이 필요했습니다.
분할 정복으로 접근하기
이 문제는 거듭제곱을 다음처럼 나누어 생각할 수 있습니다.
A^8 = (A^4) * (A^4)A^4 = (A^2) * (A^2)A^2 = (A^1) * (A^1)
즉, A^B를 구할 때 매번 하나씩 곱하는 것이 아니라,절반으로 나누어 계산한 결과를 재사용할 수 있습니다.
예를 들어 A^10을 구할 때도
A^10 = A^5 * A^5처럼 생각할 수 있고,
홀수라면 한 번 더 A를 곱해주는 식으로 처리할 수 있습니다.
이렇게 하면 문제 크기가 계속 절반으로 줄어들기 때문에 시간 복잡도를 크게 줄일 수 있습니다.
성공한 코드
#include <bits/stdc++.h>
using namespace std;
long long a, b, c;
long long power(long long x, long long y) {
if (y == 1)
return 1;
long long half = power(x, y / 2);
half = (half * half) % c;
if (y % 2 == 1)
half = (half * x) % c;
return half;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b >> c;
cout << power(a, b) % c << "\n";
}풀이 흐름
A,B,C를 입력받는다.power(x, y)를 통해x^y % c를 재귀적으로 계산한다.y를 절반으로 나누어 먼저 계산한 값을 재사용한다.- 짝수라면
half * half - 홀수라면 거기에 한 번 더
x를 곱한다. - 매 단계마다
% c를 적용해 값이 너무 커지지 않게 한다. - 최종 결과를 출력한다.
구현 포인트
1. 나머지 연산 성질 활용
이 문제의 기본 전제는 다음 식입니다.
(a * b) % c = (a % c) * (b % c)이 성질 덕분에 매 단계에서 % c를 적용하면서도 최종 결과를 유지할 수 있습니다.
즉, 큰 수를 끝까지 그대로 들고 가지 않고,
중간중간 나머지 연산을 적용해 숫자 크기를 줄일 수 있습니다.
2. 이미 계산한 값을 재사용
분할 정복의 핵심은 기존에 계산한 값을 다시 활용하는 것입니다.
long long half = power(x, y / 2);
half = (half * half) % c;여기서는 x^(y/2)를 한 번만 계산하고,
그 결과를 이용해서 전체 값을 구성하고 있습니다.
즉, 처음 실패했던 반복 방식과 달리
같은 계산을 계속 반복하지 않는다는 점이 중요합니다.
3. 홀수일 때 한 번 더 곱하기
지수가 홀수라면 절반으로 나눈 뒤 한 번 더 x를 곱해줘야 합니다.
if (y % 2 == 1)
half = (half * x) % c;이렇게 하면 짝수/홀수 경우를 모두 처리할 수 있습니다.
시간 복잡도
처음 방식은 B번 반복하는 구조라서 O(B) 였습니다.
반면 분할 정복 방식은 매번 지수를 절반으로 줄이므로
시간 복잡도가 O(log B) 가 됩니다.
이 차이 때문에 같은 문제라도
- 단순 반복은 시간 초과
- 분할 정복은 통과
가 되는 문제였습니다.
