백준, BOJ, 13458번 C++ [CPP] **

 

재귀나 숫자 범위에 대해 기본적인 문제 좋은 것 같다.

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

1629번: 곱셈

 

---

 

 

음.. 처음 봤을 때 당황 많이했다.

 

int, 4바이트

long long 8바이트

재귀함수까지...

 

재귀함수는 항상 그게 중요하다.

점화식을 찾는 것...

1번, n번 n+1번까지의 식만 찾으면 굿

 

맞는 풀이( 틀린 풀이도 집어넣어놨다.)

#include<iostream>

using namespace std;

using ll = long long;


ll remain(ll a, ll b, ll c){
    
    //n = 1일 때
    if(b == 1)return a%c;
    
    //이용하기 전 값을 리턴받고 이용
    ll val = remain(a, (b/2), c);
    val = (val * val)%c;
    
    //n = 2k 또는 n = 2k + 1일 때
    /*
    if(b%2 == 0){
        return (val*val)%c;
    }else{
        return (val*val*a)%c;
    }
    */
    
    if(b%2 == 0){
        return val;
    }else{
        return (val*a)%c;
    }
    
    
}


int main(){
    ll A,B,C;

    ios::sync_with_stdio(0);
    cin.tie(0);
    cin  >> A >> B >> C ;
    cout << remain(A,B,C);
}

 

 

 

중요한 것은

 

거듭제곱은 크기가 무지하게 빨리 커지는데..? 어떻게 처리하냐 이거다.

 

우선 long long은 2^63-1 까지의 범위를 가진다. 

즉, (2^32)-1의 제곱을 2번만 해도 벌써 위기가 찾아온다.

-> 연산결과에서 나머지를 구하는 것은 불가능하다.

 

바킹독

 

다시 말해 거듭제곱을 처리해야한다는 것인데 

총 값에서 나머지를 구하는 것이 아닌

나머지를 이용하여 다음 나머지를 구하는 것이다.

 

다시 말하면

10 1 12 일때

답은 10이다

-10 % 12

10 2 12일 때

답은 4이다.

-100 % 12

10 3 12일 때도 

답은 4이다.

-1000 %12

 

위와 같이 생각했을 수도 있다. 하지만 나는 나머지를 이용한다고 했다.

 

10 1 12

- 10

 

10 2 12

- 10 * 10 % 12

 

10 3 12

- 4 * 10 % 12

 

 

즉, 나머지를 이용하면 항상 나머지보다 작은 값으로 값의 상태를 유지하면서 나머지 계산이 가능하게 된다.

** long long을 초과하지 않음

 

 

1일 때는 그냥 나머지 값을 계산하고

2일 때는 1의 나머지의 값을 받아 제곱을 한 뒤 다시 나머지를 구한다.

3일 때는 1의 나머지 값을 받아 제곱을 한 뒤 한 번 더 곱해주고 그 후 나머지를 구한다.

 

5까지만 해보자

 

4일 때는 2의 나머지 값을 받아 제곱을 한 뒤 다시 나머지를 구한다.

5일 때는 2의 나머지 값을 받아 제곱을 한 뒤 한 번 더 곱해주고 그 후 나머지를 구한다.

 

2의 나머지는 1의 나머지 값으로 구한댔지??

 

결국 저렇게 재귀로 풀 수 있다는 것이다.