1629. 곱셈(C++)

재귀를 이용하여 푸는 문제다.

 

처음에는 정말 어려웠다. 우리가 아는 상식대로 그냥 제곱해서 풀면 안됨? 이라면서 그냥 풀어보려고 했으나..

수의 크기가 어마어마 해서 그걸로는 턱없이 부족했다.

 

강의에서 문제를 푸는 사고를 설명해줬다.

바킹독님의 알고리즘 강의 중에서

a^n * a^n = a^2n 이다. (??????????????) (뭐 어쩌라고)

그러니까 그 다음 공식을 보면 굳이 주어진 식 그대로 풀지 않고서도 반으로 나누어서 푸는 식으로도 문제의 답을 구할 수 있다라는 의미이다.

 

그 아래의 1번 도미노가 쓰러진다.

그러면 k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다라는 공식이 성립이 된다라는 뜻이다.

 

그럼 1승을 계산할 수 있다라는건,

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

 

이러면 재귀를 사용하여 문제를 풀 수 있다라는 뜻이다.

(사실 잘 모르겠다..;;;;;;;;;;;;;;;)

 

그럼 어떻게 풀어야 하는거임..

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll func(ll a,ll b, ll c) {
    if(b == 1) return a % c; // 제곱수가 1일 경우에 그냥 a를 c로 나눈 나머지를 출력한다.
    ll tmp = func(a, b /2, c); // 그게 아닐경우에 원시적인 방법으로 구하면 크기가 너무 커져서, 제곱수를 반으로 나눈 뒤 구해본다.
    tmp = tmp*tmp % c;  // 반으로 나눈 제곱수를 제곱하여 나머지를 구한다.
    if(b%2 == 0) return tmp;  // 만약 제곱수가 짝수일 경우, 그냥 tmp를 return 한다.
    return tmp * a % c;        // 만약 홀수일 경우엔 a를 한 번 더 곱해야 한다.
}




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

    ll a,b,c;
    cin >> a >> b >> c;
    cout << func(a,b,c);
}

아까 위의 사진에서 봤듯이 나누고 나누고를 시전해 다시 제곱을 만들고, 제곱수가 짝수면 그냥 출력, 아니면 한번 더 곱해주고 출력을 한다.

계속 계속 들어가는 것 같다.

 

그럼 1승을 계산할 수 있다라는건,

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

 

이 공식이 딱 성립이 되는 것이 저 코드인 것 같기 때문이다.

 

너무 어렵다 재귀.. 열심히 해보자.,,,