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

Key

시간 제한이 0.5초이고 각 수는 최대 2,147,483,647(21억 정도..)이므로 당연히 반복문 같은걸 사용하면 안된다.

거듭제곱하면 바로 생각나는 게 for문으로 곱해주기인데 이런 경우엔 반대로 큰 수를 작게 쪼개는 방법을 생각해야한다.

 

 

Idea

지수의 합 법칙과 모듈러 분배 법칙을 알아야한다 (쓸 일이 없어서 기억 저 뒷편으로 사라져버려... 검색으로 알아냈다ㅎ..)

 

지수의 합 법칙

모듈러 분배 법칙

 

2^5를 예시로 들어보자면 2^5 = 2^2 * 2^2 * 2이다.

2^2를 한번 더 쪼개면 2*2이다. 

 

이렇게 지수를 반으로 쪼갰다가 다시 곱하는 과정에서 모듈러 연산을 적용하는 방식을 통해 정답을 구할 수 있다. '반복적으로 값을 쪼개는 일'이니 재귀가 떠올랐다.

 

이 재귀함수는 지수가 1이 될 때까지 지수를 절반으로 나누는 작업을 한다.

위의 예시처럼 지수가 홀수인 경우엔 n^m/2 * n*m/2 * n을 반환하고, 짝수인 경우엔 n^m/2 * n^m/2 를 반환하는 작업을 반복한다.

그리고 지수가 1인 경우엔 n을 반환한다. 이렇게 설명하니 이해가 안 될 수 있는데, 예시를 들어보겠다.

 

2^5를 계산해야하는 상황이다.

calc(2,5)가 호출된다.

지수가 1이 아니므로 다시 calc(2,2)가 호출된다.

지수가 1이 아니므로 다시 calc(2,1)가 호출된다.

지수가 1이 되었으므로 2를 반환한다.

calc(2,2)로 돌아왔다. 지수가 2(짝수)이므로 2^2를 반환한다.

calc(2,5)로 돌아왔다. 지수가 5(홀수)이므로 2^2 * 2^2 * 2를 반환한다.

 

이렇게 곱해주는 과정에서 오버플로우가 발생할만한 지점에서 모듈러 연산을 하면 된다.\

 

나의 경우 long으로 선언했는데, c++에서 long은 최대 2,147,483,647까지 담을 수 있어서 변수 * 변수하면 바로 오버플로우가 발생한다. 그래서 모든 피연산자에 모듈러 연산을 적용했다.

 

long long 타입으로 선언해도 되지만 두 temp에 모두 모듈러 연산 적용하면 되는거라 그냥 long으로 했다.

 

Code

#include <iostream>
using namespace std;

long A = 0, B = 0, C = 0;

long calc(long A, long exp) {
	
	// 지수가 1일 때
	if (exp == 1) {
		return A%C;
	}

	int temp = calc(A, exp / 2);

	// 지수가 짝수일 때
	if (exp % 2 == 0) {
		return temp%C * temp%C;
	}
	// 지수가 홀수일 때
	else {
		return temp%C * temp%C * A%C;
	}
}

int main() {

	cin >> A >> B >> C;

	cout<<calc(A, B)<<"\n";


	return 0;
}

 

 

회고

어떻게 풀지 생각이 안나서 바로 정답을 봤던 문제이다... 분할 정복이나 그림 문제에 가장 약한 것같다. 잊을때쯤 한번 더 풀어봐야지.