[백준/1692번][C++] 곱셈

www.acmicpc.net/problem/1629

1629번: 곱셈

아직 재귀가 낯설어서 이해하는데 정말 오래걸렸다ㅠㅠ

visual studio로 디버깅하는게 편해서 오랜만에 visual studio code가 아닌 visual studio를 사용했다.

디버깅하면서 값이 어떻게 바뀌는지 다 확인했다. 먼저 코드를 제시하겠다.

#include <iostream>

using namespace std;

using ll=long long;

ll POW(ll a, ll b, ll m){
    //base condition
    if (b==1) return a%m;
    //(a^2n)=(a^n)*(a^n)
    ll val=POW(a,b/2,m);
    val=val*val%m;
    if(b%2==0) return val;//b가 짝수
    return val*a%m;//b가 홀수면 a를 한번 더 곱해야함.
}

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll a,b,c;
    cin>>a>>b>>c;

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

예시를 통해 절차적인 내용을 한 번 살펴보자.

구하고자 하는 것: 3의 9제곱을 7로 나눈 나머지

base condition을 1제곱이 됐을 때로 정했다. 즉 POW(a,1,m)일 때까지 계속 b/2를 진행하는 것이다.

b가 원래 9였는데 b/2를 만나 POW(3,4,7)이 호출된다. 

이렇게 b가 계속 b/2를 만나 2로 나눠진다.

b가 1이 되었다. 

base condition이 된 것이다.

POW(3,1,7)의 결과로 3이 반환된다.

드디어 val에 3이 저장 된다.

이 식에 의해 val이 2가 된다. 

이제 POW(3,2,7)의 값이 2인 것을 알아냈다!

POW(3,4,7)은 4

POW(3,8,7)은 16%7=2

POW(3,9,7)은 2*a%m=2*3%7=6이 나오게 된다.

 

과제로 재귀 문제를 몇번 풀었지만 사실 완전히 이해하고 푼 문제가 별로 없어서...

하나씩 생각하느라 오래 걸린 것 같다.

 

계속 강의에서 절차적으로 생각하지 말고 귀납적으로 생각하라고 했는데, 이 문제를 절차적으로 뜯어보고, 완전히 이해하고 나서야 그 말을 납득할 수 있었다.

1제곱일 때 성립한다-> k제곱일 때도 성립하면, 2k제곱, 2k+1 제곱일 때도 성립한다. 

이런 생각을 통해 문제를 재귀로 잘 해결할 수 있겠구나~를 깨달아야한다.