[PS 백준 - 4.2] 1629번: 곱셈

문제 정보

백준 1629번 - 바로가기

• 난이도: 실버 1
• 알고리즘: 분할 정복

---

코멘트

10번이나 틀린 짜증나는 문제였다. $A, B, C$ 가 $2,147,483,647$ 이하의 자연수라서 일반적인 거듭제곱 꼴로는 문제를 풀 수가 없다. 이 문제는 블로그의 도움을 미리 받고 시작해서 아이디어 자체는 쉽게 접근했다. 지수를 반씩 나누고 마지막에 합치는 형태로 풀면 된다. 근데 10번씩이나 틀리게 한 주범은 바로 나머지 연산 때문이였다. 계산 과정 중간에 나머지 연산을 하면 int형으로 간주되어 값이 삐끗나버리는 경우가 많았다. long long int 형으로 값을 미리 받아두고, 나머지 연산을 한번 해준 뒤, 제곱시킨 값에서 다시 한번 더 나머지 연산을 해주면 해결된다.

1. 분할 정복 함수 - Base Case는 B == 0, B == 1 일 때이다. 이 때는 각각 0과 A를 출력하면 된다.
2. 지수가 짝수면 2로 나눈 값을 지수로 대입하여 재귀적으로 호출하고, 홀수면 지수를 1 빼서 짝수로 만든 값을 지수로 대입하여 재귀적으로 호출하면 된다. 이 때 위에서 말한 것처럼 나머지 연산을 적절히 해줘야 한다.

---

소스 코드

#include <iostream>
#include <cmath>

using namespace std;

long long int divideConquer(long long int A, long long int B, long long int C) {
    if (B > 1) {
        if (B % 2 == 0) {
            long long int x = divideConquer(A, B / 2, C);
            x %= C;
            return (x * x) % C;
        }
        else
            return divideConquer(A, B - 1, C) * A; // 짝수로
    }
    else if (B == 1){
        return A;
    }
    else if (B == 0) {
        return 1;
    }
}

int main() {
    int a, b, c;
    cin >> a >> b >> c;

    cout << divideConquer(a, b, c) % c; 
}