[알고리즘] 백준 1629번: 곱셈 (C++), 분할 정복 개념, 분할 정복을 이용한 거듭제곱

이번 문제는 당연하게 나머지 정리(MOD의 연산)를 이용해 풀 수 있을 거라 생각했다.

왜냐하면 거듭제곱을 할수록 수는 기하급수적으로 엄청 커질 것이기 때문에 즉각적으로 이를 처리할 수 있는 나머지 정리를 사용하는 것이 필수적이라 생각했다.

 

하지만, 거듭제곱의 연산 또한 2,147,483,647 이하의 수가 주어지기 때문에 시간 초과를 발생시킬 것이라 확신했다.

어떠한 솔루션이 떠오르지 않았고, 이 문제는 '분할 정복을 이용한 거듭제곱' 이란 키워드로 분류되어있었기 때문에 분할 정복에 대해 알아보기로 했다.

---

이번 문제에서 사용된 나머지 정리 연산 규칙성

(A * B) mod N = (A mod N * B mod N) mod N

가정: 어떠한 값을 A라 두고, 나누는 수가 N이라고 했을 때 A mod N은 idx라고 한다.

b가 1일 때 -> idx

b가 2일 때 -> idx * (idx mod N)

b가 3일 때 -> idx * (idx mod N) * (idx mod N)

b가 4일 때 -> idx * (idx mod N) * (idx mod N) * (idx mod N)

...

다음과 같은 규칙성을 지닌다고 해서 idx^4 * (mod N)^3 같은 수식으로 정리하는 것은 말이 되지 않는다.

(나누기로 착각할 수 있지만 %는 나머지를 구하는 연산이기 때문이다.)

 

[작성했던 코드]

우선 b가 1이더라도 나머지를 도출해야 하기 때문에 idx = a % c라는 코드를 짰다.

나머지는 위에서 작성한 규칙성을 코드로 적었다.

#include <iostream>
#include <vector>
#define ll unsigned long long
using namespace std;

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

	ll a, b, c;
	cin >> a >> b >> c;
	
	ll idx = a % c;
	
	for (int i = 1; i < b; i++) {
		idx *= a;
		idx %= c;
	}

	cout << idx;
	return 0;
}

맨 위에서 말한 대로 거듭제곱의 연산 수도 엄청나게 큰 수일 수도 있기 때문에 이는 시간 초과를 발생시킬 것이다.

 

---

분할 정복(divide and conquer) 개념

분할 정복의 개념은 내가 느끼기엔(주관적) DP와 유사하다고 생각했다. 아무래도 DP가 작은 문제를 풀어나가면서 큰 문제를 풀어나가는 데에 도달하는 점과 분할 정복이 큰 문제를 작은 문제(같은 크기)로 나누어 재귀적으로 풀어나간다는 점이 비슷하게 느껴졌다.

하지만, DP는 작은 문제들을 풀어나가면서 큰 문제에 '도달'하지만

분할 정복은 작은 문제들을 풀어서 이를 '병합'시켜 큰 문제의 답을 도출해낸다.

---

풀이

당연하게도 알고리즘의 개념만 가지고서는 풀 수 없었다.

+참고한 블로그(https://hugssy.tistory.com/34)

예를 들어 입력값이 3 3 7이라고 하면 수기로 답을 구했을 때는 6이다.

다음 코드도 같은 답을 출력하는지 시뮬레이션을 해보자.

#include <iostream>
#include <vector>
#include <cmath>
#define ll unsigned long long
using namespace std;

ll POW(ll a, ll b, ll c) {
	if (b == 0) {//지수가 0이면 모든 수가 1이 된다.
		return 1;
	}
	ll idx = POW(a, b / 2, c); // 여기서 분할적으로 나뉘어짐
	idx = idx * idx % c;
	
	if (b % 2 == 0) {// b가 짝수일 때
		return idx;
	}
	else {// b가 홀수일 때
		// a를 한 번 더 곱해줬기 때문에 여기서 한 번 더 나머지연산이 필요하다.
		return idx * a % c;
	}
}

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

	ll a, b, c;
	cin >> a >> b >> c;
	
	cout << POW(a, b, c);
	return 0;
}

 

[시뮬레이션]
POW(3, 1, 7)
우선 b가 0이 아니기 때문에 POW(3, 1, 7)이 call 된다.
또다시 b가 0이 아니기 때문에 POW(3, 0, 7)이 call 된다.
b가 0이기 때문에 POW(3, 0, 7)에 대한 리턴 값 1이 리턴되고,
POW(3, 1, 7)을 수행한다.
idx = idx * idx % c에 의해 1이 도출된다.
그리고, b가 1, 홀수이기 때문에 1에다가 3을 곱해주고, 7을 나누면
POW(3, 1, 7)에 대한 리턴 값 3이 리턴된다.
다시 idx = idx * idx % c에 의해 2가 되고,
b는 3, 홀수이기 때문에 최종적으로 리턴하는 값은 6이 되므로
수기로 구한 답과 일치한다.

 

사실상 이 코드를 시뮬레이션 돌린 것은 큰 의미가 없었다.

시뮬레이션하면서 분할 정복이라는 알고리즘에 다가가려 했지만 분할적으로 생각한다는 개념 말고는 큰 수확이 없는 듯했다.

분할 정복 관련 문제들을 여러 개 풀어보면서 공부를 해봐야 할 거 같다.

언제 분할 정복을 떠올리는지 키포인트가 무엇인지