[BOJ] 1629. 곱셈 (C++) (분할정복)

• 코딩초보
• 분할정복 

---

1629. 곱셈 (실버1) 

 

문제

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

입력

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

출력

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

 

 

#include <iostream>

using namespace std;

long long a, b, c,tmp; 

//b가 짝수일 경우: a^b = a^(b/2)*a^(b/2) 
//b가 홀수일 경우: a^b = a^(b/2)*a^(b/2 +1) 
//long long 은 9,223,372,036,854,775,807까지 표현 가능. 사실상 무제한의 정수 범위. 

long long pow(long long b) {
	if (b == 0) return 1; 
	if (b == 1) return a % c; 

	tmp = pow(b / 2) % c; //중복 재귀호출 방지 

	if (b % 2 == 0) return tmp * tmp%c; 
	return tmp * tmp%c * a % c; 
}


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

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

	
	return 0;
}

 

분할정복 알고리즘을 이용하는 문제다. 

처음에 감이 안잡혀서 이분의 코드( https://velog.io/@junttang/BOJ-1629-%EA%B3%B1%EC%85%88-%ED%95%B4%EA%B2%B0-%EC%A0%84%EB%9E%B5-C) 를 참고하여 공부했다. 다음에 비슷한 분할정복 문제가 나오면 또 잘 풀 수 있어야 할텐데..! 

 

분할 정복이란, 함수를 재귀적으로 호출하여 큰 문제를 작은 문제들로 분할하여 solve하는 알고리즘이다. 위와 같이 거듭제곱과 같은 문제를 해결할 때 많이 사용하는 알고리즘이다. 

 

 

위와 같이 큰 수를 거듭제곱할때, c로 나눈 나머지를 구해야하므로 함수에서 거듭제곱을 다 한 후 c로 나누지 말고, 호출할때 c로 나눈 나머지를 가지고 계산을 하는 것이 더 효율적이다. 

 

이때 b가 짝/홀일때의 경우를 나눠서 문제를 쪼갤 수 있다. 

 

b가 짝수일 경우: a^b = a^(b/2)*a^(b/2)

b가 홀수일 경우: a^b = a^(b/2)*a^(b/2 +1) 

로 표현 가능하다. 

 

 

따라서 b가 1이 될때까지 문제를 쪼개는 base case로 생각해야한다. 

 

여기서 위의 블로그 글에서 참고했듯이, tmp를 사용하여 중복 재귀호출을 방지해야한다. (중복호출은 시간초과를 일으킨다!) 

 

tmp를 통해 중복호출을 방지하고 그 값을 기억하도록 한다. 그리고 b가 짝수일 경우 tmp*tmp %c를 return하고, b가 홀수일 경우 tmp*tmp%c*a%c를 해준다. 여기서 c를 나눠주는 이유는 (A*B) % C = (A%C * B%C) %C의 성질을 사용했다.