[백준] 1629 곱셈 by C++

https://www.acmicpc.net/problem/1629

1629번: 곱셈

재귀를 제대로 이해하고, 수에 관한 통찰력도 요구하는 문제다.

 

핵심함수

Recur : A, B, C를 입력 받고 A ^ B % C (나머지)의 값을 반환

 

 

알고리즘 방식

방식이라기보다는 2가지만 명확히 이해하면 어렵지 않게 풀 수 있다.

1.  재귀
2. A^B % C = [A^(B / 2) % C] * [A^(B / 2) % C] * [A^(B % 2) % C] % C

2번 방식만 설명하면 될 것 같은데,

1. A^B % C는 X * C + Y (X = 몫, Y = 나머지)로 나타낼 수 있다.
2. (X1 * C + Y1) * (X2 * C + Y2) = X1*X2*C^2 + (X1*Y2 + X2*Y1)C + Y1*Y2가 되므로 
   이 값을 C로 나눴을 때의 나머지를 구하려면, Y1 * Y2 % C만 연산하면 된다.
   (앞에는 C를 인수로 가지고 있기 때문에 몫의 일부분이 됨
   또한, A^B를 구한 후 %C를 할 경우 수가 너무 커져서 메모리 초과가 발생하므로 이 원리를 사용해야 함)

 

재귀 알고리즘 사고 방식 (개인 메모)

1. Base Condition, 즉 재귀문의 끝이 되는 상황에서 어떤 결과를 반환할지를 생각해야한다.
   일반화해서 귀납법으로 얘기하자면, N이 1 ~ n의 범위일 때,
   N이 1에서 시작할 경우 N이 Base Condition이 될 것이고
   N이 n에서 시작할 경우 1이 Base Condition이 될 것이다.
   일반적으로 재귀함수가 반환하길 원하는 형태의 값 (이 문제에서는 나머지)을 반환하도록 한다.
2. 위에 가정한 상황에서 N이 n에서 시작할 경우 Base Condition은 1이될테고,
   차례대로 n = 2일때, n = 3일 때....을 생각해보면서 재귀 함수를 작성해야한다. 

 

시간복잡도 계산 (추측...?)

for (int i = 1; i < N; i * 2)일 때

이므로

 

1. for (int i = B; i >= N; i / 2) 

 

2. 이 문제에서 N = 1이므로,

    for (int i = B; i >= 1; i / 2)

   (사실 1번 수식에 N = 1을 대입하면 됨)

 

따라서 해당 문제의 시간 복잡도 O(n) = logN 또는 logB이다.

 

소스코드

#include <iostream>

using namespace std;

#define ll long long

ll Recur(ll A, ll B, ll C) {
	if (B == 1) {
		return A % C;
	}
	ll remainder = Recur(A, B / 2, C);

	if (B % 2 == 0)
		return remainder * remainder % C;
	else {

		//return remainder * remainder * A % C;
		//위와 같이 작성하면 에러가 발생
		//이유는 raminder의 최대값은 int 양의 최대값 -1, 대략적으로 10^9이고 이 두 수를 곱하면 최소 10^18
		//long long의 범위는 10^18이므로, reaminder의 제곱에 A를 곱할 경우 높은 확률로 오버플로우가 발생
		remainder = remainder * remainder % C;
		return remainder * A % C;
	}


}

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

	ll A, B, C;
	cin >> A >> B >> C;

	cout << Recur(A, B, C);
}

* basecondition을 0으로 할 경우

if (b == 0)
	return 1;