[백준]1629번 곱셈 c/c++

baaaaarking dog님 알고리즘 강의를 참고한 내용입니당

문제

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

1629번: 곱셈

설명

재귀 문제를 풀때 절차지향적 사고로 풀기보단 귀납적 사고로 푸는것이 좋다.
(절차지향적 사고로 생각하려다가 머리속이 꼬일 수 있기때문에)

그럼 귀납적 방법이란게 뭐냐??

1번 도미노가 쓰러진다
k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다.

이 문제는 b가 최대 21억 가까이 되기때문에 시간초과가 발생할 것이다.

이 사진의 로직을 이용하면

1승을 계산할 수 있다.
k승을 계산했으면 2k승과 2k+1승도 O(1)에 계산할 수 있다.

코드

#include<iostream>
using namespace std;
using ll = long long;

ll POW(ll a, ll b, ll m)
{
	if (b == 1)
		return a % m;  //base condition
	ll val = POW(a, b / 2, m);
	val = val * val % m; 
	if (b % 2 == 0)
		return val;
	return val * a % m;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll a, b, c;

	cin >> a >> b >> c;

	cout << POW(a, b, c);
}

9번째 줄에 POW(a, b / 2, m)를 즉 a^(b/2) mod m을 val에 저장해주었다.
그리고 val을 제곱해주었다.
만약 b가 7이라고 한다면 b/2는 3이니 10번 줄이 끝났을 때 val은 a^6 mod m의 값이 들어갈 것이다.
즉 b가 짝수이면 그냥 val의 값을 반환하면 끝이지만 b가 홀수이면 val에 a를 한 번 더 곱해서 반환해야 한다.


즉 base condition을 잘 잡아뒀고 k승의 결과를 토대로 2k, 2k+1승의 결과를 계산할 수 있으니
마치 도미노를 쓰러트리는 것 처럼 모든 결과가 잘 계산될 것이다로 함수를 이해할 수 있어야한다!!!!

이 함수의 시간복잡도는 b가 절반씩 계속 깎이기 때문에 O(log b)이다.