[백준 1629번/C++] 분할 정복 곱셈

처음 이 문제를 봤을 때 분할 정복으로 나눌 방법을 찾지 못해서 DC함수를 만들고 반복문 안에서 DC함수를 불러왔다.

DC함수 안에서는 계속 곱한 수의 나머지에 A를 곱하고 %C를 한.. 

작은 수에서는 괜찮았는데 아무래도 A, B, C 모두 최대 21억이다보니 long long으로 받아도 안됐었다.

그래서 반복문은 포기, B를 계속 2로 나눠서 수를 낮추는 방법으로 했다.

 

여기서 계속 %C를 해주는 것을 모듈러 연산이라고 하는데, 

모듈러 연산: 정수들 간의 산술 연산을 특정 모듈로 나눈 나머지를 구하는 연산

으로, 결과를 0부터 모듈 값까지 범위로 제한한다. 이를 통해 오버플로를 방지할 수 있다.

• 답

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int DC(int A, int B, int C)
{
    if (B == 1) return A % C;

    long long tmp = DC(A, B / 2, C) % C;

	// 예를 들면 7을 2로 나눈 몫은 3으로, 3+3이 되면 1이 모자라므로 A를 한번 더 곱해줌
    if (B % 2) return tmp * tmp % C * A % C;
    else return tmp * tmp % C;

}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int A{}, B{}, C{};
    cin >> A >> B >> C;
    
    cout << DC(A, B, C);
}

 

알게 된 점: 모듈러 연산(많이 해도 계산의 오류가 날 확률 적음)