문제 이해 단계
https://www.acmicpc.net/problem/1629
1629번: 곱셈
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
www.acmicpc.net
입력으로 A, B, C가 들어온다.
자연수 A를 B번 곱하고, C로 나눈 나머지를 출력해라.
문제 접근 단계
상당히 간단한 문제로 보인다. 하지만 그렇지 않다.
여기에는 2가지의 문제점이 존재한다.
첫 번째는, 수의 범위이다.
제한사항을 보면 입력이 2,147,483,647까지다.
입력부터 20억이 넘어가기 때문에 20억^20억
long long int 자료형을 아득히 넘어간다.
그렇기 때문에 지수를 한 번에 곱해서 구해서는 안된다.
자료형을 넘지 않도록 지수를 분할하여 곱하여야 한다.
두 번째는 시간복잡도이다.
그럼 한 번씩 곱할 때마다 나머지를 구하면 되지 않을까?
이러면 시간복잡도가 O(n)이 되는데,
해당 문제의 시간제한이 0.5초로 시간초과가 뜬다. 그래서 다른 방법을 사용해야 한다.
결론적으로 이 문제는 분할정복을 사용하여 자료형을 넘지 않도록 하고
O(logN)의 시간복잡도로 실행되게 한다.
이 문제는 지수(B)의 짝수일 때와 홀수일 때를 구분해야 한다.
예를 들어, 2^10 같은 짝수일 경우, (2^5)*(2^5)로 분할할 수 있다.
하지만 2^11 같은 홀수일 경우에는, 분할을 하면 정확히 반으로 나눠지지 않기 때문에
2를 하나 밖으로 빼두어 (2^5)*(2^5)*2 이런 식으로 형식을 맞춰준다.
2^5는 또한 반으로 나눌 수 있다.
(2^2)*(2^2)*2.. 이런 식으로 계속해서 재귀적으로 반으로 나눠갈 수 있다.
결국 이 문제는 b의 홀짝을 잘 구분해서
재귀호출을 해주면 되는 문제이다.
여기서 핵심은 해당 값을 변수에 담을 때, 항상 C로 나눠준 나머지를 담아야 한다.
그렇게 하지 않으면 자료형을 넘어가는 값이 나올 수도 있기 때문이다.
자세한 것은 문제 구현 단계에서 설명하겠다.
문제 구현 단계
#include <iostream>
#include <cmath>
using namespace std;
long long solve(long long a, long long b, long long c){
if(b == 0) return 1;
long long temp;
temp = solve(a,b/2,c); // 지수를 절반 나눠서 재귀 호출
temp = temp*temp%c; // c로 나눈 나머지를 temp에 저장
if(b % 2 == 0) return temp; // 짝수일 경우
else return temp*a%c; // 홀수일 경우 a를 곱해서 다시 c로 나눠줌
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
long long A,B,C;
cin >> A >> B >> C;
cout << solve(A,B,C);
}핵심적으로 봐야 할 것은 solve 함수 부분이다.
예외처리로 지수(b)가 0일 때 1을 반환해 주는 것을 해준다.
temp에는 지수를 절반으로 나눠 재귀호출하여 이를 C로 나눈 나머지를 저장한다.
이때 무조건 C로 나눈 나머지를 저장해야 한다.
왜냐하면 값이 long long을 넘어갈 수도 있기 때문이다.
그 후 b가 홀수인지 짝수인지 판단해 주고
짝수라면 그대로 반환,
홀수라면 a를 한번 더 곱해주고 다시 c를 나눠주고 반환해 준다.
전체코드에 대한 설명은 여기까지이다.
시행착오
분할정복에 대한 문제는 처음 풀어본 것 같다.
왠지 그렇게 와닿는 문제는 아니었던 것 같다.
뭔가 새로운 유형을 풀어본 것 같아서 당황스럽기도 했다.
인터넷을 참고 안 했으면 못 풀었을 듯...
생활비..