BOJ - 1629 곱셈 해결 전략 (C++)

• 문제 링크
  백준 1629번 - 곱셈

해결 전략

  본 문제는 "똑같은 결과를 내는 중복되는 재귀호출은 값을 기억하는 방식으로 처리하는 것이 바람직하다."라는 교훈을 얻을 수 있는 문제이다.

  그 이유를 설명하기에 앞서, 본인은 최초 시도에서 이 문제를 해결하지 못했는데, 그 이유는 문제를 '거듭제곱'에 집중하지 않고, '큰 수의 곱셈'에 집중해서, 계속해서 Strassen 식의 해결을 시도했기 때문이었다.

문제가 요구하는 상황이 무엇인지를 명확히 파악하는 것이 PS의 가장 첫 번째 센스이다.

  이 문제에서 요구하는 것은, 큰 수의 곱셈이 아니라, '큰 수의 거듭 제곱'이다.

  큰 수의 거듭제곱이란 문제 상황을 맞딱뜨리면, 바로 떠올릴 수 있는 풀이 방법은 아무래도 Divide & Conquer이다. 빠르게 수를 쪼개 값을 계산할 수 있기 때문이다.

  거듭제곱과 관련된 분할 수식은 무엇이 있을까? 이 역시 어렵지 않게 떠올릴 수 있다.

b가 짝수이면 : a^b = a^(b/2) x a^(b/2)
b가 홀수이면 : a^b = a^(b/2) x a^(b/2 + 1)

  일 것이다.

  문제 상황을 정확히 파악하고, 분할정복 알고리즘까지 떠올렸다면, 이 수식을 생각하기는 결코 어렵지 않다. 하지만, 문제는, 여기서도 한 번의 숙련도가 필요한 것이, 예를 들어 아래의 코드와 같이 Naive하게 분할정복을 구성하면 문제가 발생한다.

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

  b가 C++ 기준 Int자료형의 최대 범위인 2,147,483,647까지 가능하기 때문에 위의 수식대로 power함수를 구성하면, 최대 입력 상황에서 시간 초과 혹은 오버플로우가 나게 된다.

너무 많은 중복 재귀호출의 발생은 결코 바람직한 코드가 아니다. 시간 효율적으로도, 메모리 관점에서도 말이다.

  그래서, 이때, 중복 호출을 한 번의 호출로 처리하고, 그 값을 기억하는 스킬이 필요하다. 불필요하고 느린 재귀연산을 많이 하는 것을 방지할 수 있다.

long long power(long long b) {
	if (b == 0) return 1;
	if (b == 1) return a % c;
	
	k = power(b / 2) % c;
	if (b % 2 == 0) return k * k % c;
	return k * k % c * a % c;
}

  이 문제는 바로 이 센스를 발휘하는 것이 핵심인 문제였다.

  한편, 반환값을 long long으로 처리해주는 것도 중요하다. long long은 9,223,372,036,854,775,807까지 표현이 가능한, 사실상 무제한의 정수 범위를 제공하기 때문이다. 이는 2,147,483,647 x 2,147,483,647까지는 커버가 가능함을 직접 계산해보면 알 수 있다. 따라서, Modular 연산을 함께 하고 있으므로 long long 반환값과 변수 크기면 이 문제를 해결하는데 문제가 발생하지 않는다.

  아래는 코드이다.

#include <iostream>
// BOJ - 1629 Multiplication
using namespace std;
// a^b = a^(b/2) x a^(b/2)		2147483647
long long a, b, c, k;

long long power(long long b) {
	if (b == 0) return 1;
	if (b == 1) return a % c;
	
	k = power(b / 2) % c;
	if (b % 2 == 0) return k * k % c;
	return k * k % c * a % c;
}

int main(void) {
	cin >> a >> b >> c; 
	cout << power(b);

	return 0;
}