백준 1627번 - 곱셈

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

1629번: 곱셈

 

풀이 과정

 모듈러 연산과 분할 정복을 알아야 풀 수 있다. '( A  *  B ) % C = ( A % C ) * ( B % C ) % C' 와  2^2 * 2^2 = 2^4 와 같은 사실을 이용한다. 재귀 함수를 만들어 b번 일어날 연산을 log(2)b (로그 2의 b)번 까지 줄여준다. b == 1이 되면 돌아오도록 조건을 걸고, 재귀를 빠져나오며 연산이 수행된다. 연산이 수행될 때는 수가 너무 커지지 않도록 모듈러 연산 개념을 이용해서 수를 계속 줄여준다. 그리고 마지막 리턴 전에 b가 홀수라면 a를 1회 더 곱해줘야하므로 b%2 == 1일 경우 a를 한번 더 곱하고 모듈러 연산 해주었다.

 

느낀 점

 다른 문제도 마찬가지지만 비슷한 문제를 몇번 풀어보며 체화해야될 것이라 보인다. 결국 다른 사람들의 코드를 참고한 후 풀 수 있었고 기본적인 수학 개념을 보충해야될 필요성을 느꼈다. 또 분할 정복과 모듈러 연산은 연산 횟수를 획기적으로 줄이기 때문에 반드시 짚고 가야할 개념이다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c, ret;

ll re(ll a, ll b, ll c) {
	if (b == 1) return a % c;
	ll temp = re(a, b / 2, c);
	temp = (temp % c) * (temp % c) % c;
	if (b % 2 == 1)temp = (temp % c) * (a % c) % c;
	return temp;
}

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

	cin >> a >> b >> c;

	ret = re(a, b, c);

	cout << ret << "\n";

	return 0;
}