[cpp 알고리즘] 백준 1629 곱셈

[백준] 1629 곱셈 cpp 풀이

수학, 분할 정복을 이용한 거듭제곱

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

문제 요약

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어졌을 때, A를 B번 곱한 수를 C로 나눈 나머지를 출력하면 된다.

풀이 정리

- 분할 정복을 활용하여 지수를 나누어 주면 된다.

    (1) 지수가 0인 경우 -> X^0 = 1 이므로 1을 리턴해준다.

    (2) 지수가 짝수인 경우 -> X를 X/2로 나누어서, 계산한 두 값을 곱해준다.

    (3) 지수가 홀수인 경우 -> X를 X/2로 나누고, 계산한 두 값과 밑을 한 번 더 곱해준다.

 

- 예제에 나왔던 A=10, B=11로 예를 들어 보면, 

 1. 가장 나이브하게 먼저 생각나는 방법은 for문을 이용하여 A를 B번 곱해서 A^B를 구하는 것이다. 

     for문을 이용해 ans = 1에서부터  ans * 10을 11번 반복하면 될 것이다. -> 11번

 2. 분할 정복을 활용하는 방법을 계산해보겠다. 편의상 %C는 생략했다. 

    (1) A=10, B=11 -> 11%2 == 1이므로, half = divide(10, 5)

    (2) A=10, B=5 -> 5%2 == 1이므로, half = divide(10,2)

    (3) A=10, B=2 -> 2%2 == 0 이므로, half = divide(10, 1)

    (4) A=10, B=1 -> 1%2 == 1 이므로, half = divide(10, 0)

    (5) A=10, B=0 -> B==0이므로, return 1

    (4) A=10, B=1 -> 1%2 == 1 이므로, half = divide(10, 0) = 1 -> return 1 * 1 * 10;

    (3) A=10, B=2 -> 2%2 == 0 이므로, half = divide(10, 1) = 10 -> return 10*10;

    (2) A=10, B=5 -> 5%2 == 1이므로, half = divide(10,2) = 100 -> return 100*100*10;

    (1) A=10, B=11 -> 11%2 == 1이므로, half = divide(10, 5) = 100000 -> return 10000*10000*10;

이런 과정으로 계산된다. -> 5번

C++ 코드

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

ll A,B,C;

ll divide(ll A, ll B){
    if (B==0){
        return 1;
    }
    else if (B%2==0){
        ll half = divide(A, B/2);
        return half * half % C;
    }
    else{
        ll half = divide(A, B/2);
        ll ans = half * half % C;
        return ans * A % C;
    }
}

int main() {
    cin >> A >> B >> C;
    
    cout << divide(A,B);
    
    return 0;
}

 

1%에서 틀렸습니다.

가 나왔었는데, 그 이유는 곱할 때마다 %C를 해주지 않아서, 범위가 넘어가는 문제였다. 

아래 코드가 있다. 

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

ll A,B,C;

ll divide(ll A, ll B){
    if (B==0){
        return 1;
    }
    else if (B%2==0){
        ll half = divide(A, B/2);
        return half * half % C;
    }
    else{
        ll half = divide(A, B/2);
        return half * half * A % C;
    }
}

int main() {
    cin >> A >> B >> C;
    
    cout << divide(A,B);
    
    return 0;
}