[BOJ 1629] 곱셈 (C++)

곱셈 (Silver 1)

문제

전체 문제 보기

1629번: 곱셈

접근법

이 문제는 A를 B번 곱한 값을 C로 나머지를 구하는 문제이다. 그런데 B느 최대 2,147,483,647로 굉장히 크다는 것이 문제이다. Brute force 방식으로 A를 B회 곱하기에는 B가 너무 크다. Brute force보다 더 나은 방식을 찾아야 한다. 나머지 연산은 \((a \bmod\ c * b \bmod\ c)\bmod\ c = (a * b) \bmod\ c \)와 같이 연산 중간중간에 나머지 연산을 한 결과와 전체 결과에 나머지를 구한 결과가 같다. 우리는 이 특징을 활용하여 곱셈 문제를 분할해서 풀 수 있다.

 

예를 들어서 \(7^{16} \bmod\ 13 \)을 구해보자. \(7^{16} \bmod\ 13\)은 \( ((7^8) \bmod\ 13 * (7^8) \bmod\ 13) \bmod\ 13 \)을 구하는 문제로 나눠질 수 있다. \(7^8\bmod\ 13\) 을 한 번 구하면 7을 8번곱하는 대신 \(7^8 \bmod\ 13 \) 에 \(7^8 \bmod\ 13 \)을 한번 곱하기만 하면 된다. 마찬가지로 \(7^8 \bmod\ 13 \) 문제는 \(7^4 \bmod\ 13 \) 문제 두 개로 나눌 수 있다. 이를 반복하면 \(7^{16} \bmod\ 13 \)을 구하는 문제를 \(7^2 \bmod\ 13 \), \(7^4 \bmod\ 13 \), \(7^8 \bmod\ 13 \) 을 구하는 문제로 나눌 수 있다. 즉 Brute force로 풀이할 경우 \(O(B)\)의 연산이 요구되지만 곱셈을 분할하여 문제를 풀게 되면 \(O(\mbox{log}B)\)만에 해결할 수 있다는 것이다. 같은 방법으로 \(7^{23} \bmod\ 13 \)을 구하는 문제는 \((7^{16} \bmod\ 13 * 7^4 \bmod\ 13 * 7^2 \bmod\ 13 * 7^1 \bmod\ 13) \bmod\ 13 \)을 구하는 문제로 나눌 수 있다.

 

이러한 접근법으로 만들어진 알고리즘이 Fast Algorithm이다. Fast Alogrithm의 의사코드는 다음과 같다. (\(b_i\)는 B의 이진수 i번째 값을 뜻한다.)

 

코드 구현

위 의사 코드를 아래와 같이 구현하였다. 먼저 B의 값으로 이진수 배열b[]을 구한 뒤 Fast Algorithm을 사용하였다.

#include <iostream>

#define endl '\n'
using namespace std;

int main() {
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    // 첫째 줄에 a를 B번 곱한 수를 n로 나눈 나머지를 출력한다.
    long long a, B, n; // a, B, n는 모두 2,147,483,647 이하의 자연수

    cin >> a >> B >> n;

    int b[32]{};
    // 이진수 배열로 변환
    long long temp = B, k = 31;
    for (int i = 0; i < 32; ++i)
    {
        b[i] = temp % 2;
        temp >>= 1;

        if (temp == 0)
        {
            k = i;
            break;
        }
    }

    long long c = 0, f = 1;

    for (int i = k; i >= 0; --i)
    {
        c *= 2;
        f = (f * f) % n;

        if (b[i] == 1)
        {
            c += 1;
            f = (f * a) % n;
        }
    }
    cout << f << endl;

    return 0;
}

성능평가

시간 복잡도는 앞서 설명한바와 같이 Brute force로 풀이할 경우 \(O(N)\)인 곱셈 연산을 Fast Algorithm으로 \(O(\mbox{log}n)\)으로 줄였다. 공간 복잡도는 \(O(1)\)이다.