[백준] 곱셈(1629) (C++)

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

분석

문제만 보면 간단해 보이지만 0.5초라는 시간제한이 존재하고 A를 B번 제곱하는 과정에서 오버플로우가 발생할 수 있어 까다로운 문제였다.
위에서 말한 문제점들로 인하여 오버플로우를 막고 연산횟수를 최대한 줄이는게 문제를 해결의 포인트로 생각된다.

해결방법

1. 모듈러 성질

(a b) % c = (a%c b%c) % c

2. 분할 정복 (Divide and Conquer)
분할 정복 알고리즘

크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하는 알고리즘으로 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄어가는 방식이다.

분할: 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.

정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.

조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.

모듈러 성질을 이용하여 오버플로우의 발생을 예방할 수 있으며 분할 정복 알고리즘을 지수에 적용하여 곱셈 연산의 횟수를 줄일 수 있다.
> ##코드

#include<iostream>

using namespace std;

long long power(int, int, int); 
int main() {
	int a, b, c;
	cin >> a >> b >> c;
	long long ans = power(a % c, b, c);
	cout << ans << endl;
}

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

결과

+후기
분할 정복의 구현은 간단하게 해결이 되었지만 오버플로우를 해결하는것에 어려움을 많이 겪었는데 함수의 반환형을 int로 사용하거나 곱셈 도중 %c연산을 안해주었던 것 등등 여러 이유로 오버플로우를 막지 못하여 많이 틀렸다...