[C++] BOJ 1629번: 곱셈

학교에서 진행하는 수업에서 적절한 알고리즘 문제를 찾아보고 공유하게 되었다. 가능하면 문제 설명이 간결한 문제를 찾고 싶었고, 백준 사이트에서 적절한 난이도의 문제를 찾게 되었다.

문제 링크

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

문제 분석

해당 문제는 정답률이 2024년 3월 기준 약 27%로 꽤 낮은 편에 속한다. 이는 문제의 시간 제한이 0.5초여서 생각보다 단순히 접근하면 틀리기 쉬운 문제이기 때문으로 보인다.

예를 들어 문제의 입력 조건과 시간 제한을 확인하지 않고 아래와 같은 코드를 작성하면 '틀렸습니다'가 출력된다.

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

    cin >> A >> B >> C;

    // A를 B번 곱하고 C로 나눈 나머지를 출력하는 코드
    int result = 1;
    for(int i=0; i<B; i++) result *= A;
    result %= C;
    cout << result << '\n';

    return 0;
}

이는 A의 B승을 계산하는 과정에서 오버플로우가 발생하고, 입력에 따라 시간이 0.5초를 초과하는 연산이 발생하기 때문이다. 그렇다면 해당 문제를 풀기 위해서는 어떻게 접근해야 할까?

1. C++로 문제를 풀 때에는 문제에 주어진 조건에 따라 A의 B제곱을 계산할 때 오버플로우가 발생하지 않도록 주의해야 한다. int 타입에는 A의 B승을 담지 못할 수 있으므로 8 byte의 정수를 담을 수 있는 long long 타입의 사용이 필요하다.
2. 0.5초 내에 문제를 풀기 위해서는 분할 정복 방식으로 문제를 푸는 것이 필요하다.

문제 풀이

먼저 분할 정복 방식을 어떻게 적용할지 이야기해보자. 해당 문제는 A의 B승을 빠르게 계산하는 게 중요하다. A의 B승을 A^B라고 표현하기로 하자.

A^B에 대해서 다음 식이 성립한다.

1. B가 짝수인 경우
   A^B = A^(B / 2) * A^(B / 2)
2. B가 홀수인 경우
   A^B = A^(B / 2) * A^(B / 2) * A
   이 때 / 연산자는 나누기에 대한 몫 연산자이다.

위 식대로 A, B, C를 파라미터로 전달받아 A^B을 C로 나눈 나머지 값을 계산하는 함수를 작성해 보자.

long long solution(int A, int B, int C)
{
    if (B == 0)
        return 1;
    long long result = (solution(A, B / 2, C) * solution(A, B / 2, C)) % C;
    if (B % 2 == 1)
        result = (result * A) % C;
    return result;
}

이 때, 위의 코드에서 solution(A, B / 2, C) * solution(A, B / 2, C)을 계산할 때 같은 값에 대해 2번 계산하는 문제가 발생한다. 이 문제를 해결하기 위해 함수를 다음과 같이 변경한다.

long long solution(int A, int B, int C)
{
    if (B == 0)
        return 1;
    long long result = solution(A, B / 2, C);
    result = (result * result) % C;
    if (B % 2 == 1)
        result = (result * A) % C;
    return result;
}

result 변수에 solution(A, B / 2, C) 값을 담아주고 result = (result * result) % C를 통해 중복되는 값을 2번 계산하는 문제를 해결하였다.

전체 코드

전체 코드는 다음과 같다.

#include <iostream>

using namespace std;

long long solution(int A, int B, int C)
{
    if (B == 0)
        return 1;
    long long result = solution(A, B / 2, C);
    result = (result * result) % C;
    if (B % 2 == 1)
        result = (result * A) % C;
    return result;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int A, B, C;

    cin >> A >> B >> C;

    cout << solution(A, B, C) << '\n';

    return 0;
}

결과

풀 때마다 틀리는 문제이다. 볼 때마다 새롭다...

그 외

A, B, C = map(int, input().split())
print(pow(A, B, C))

역시 없는 게 없다는 파이썬. 이 문제를 두 줄만에 해결할 수 있다...