[백준/BOJ] 1629번: 곱셈 ( 분할 정복법 ) - C++ 문제 풀이

 

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/1629

 

풀이

자연수 A를 B번 곱한 수를 구하는 문제입니다.

 

당연히, A, B에 큰 수가 입력됐을 때 글자 그대로 A^B ( A * A * A * A *... )의 계산을 하면 시간제한에 걸립니다.

 

이런 경우에 분할 정복법을 쓰게 되면 계산 시간을 상당히 줄일 수 있습니다.

 

분할 정복법은 재귀적으로 자신을 호출하면서 조건에 맞을 때까지 그 연산의 단위를 조금씩 줄어가는 방식입니다.
큰 문제를 작고 풀기 쉬운 문제로 나눠 푼 후, 그 결과를 조합해 원래 문제의 답을 구하는 방식이라고 할 수도 있습니다.

 

예를 들어, 2^10 = 2^5 * 2^5로 분할할 수 있고, 이제 2^5의 계산만 하면 2^10의 값을 알 수 있습니다.

분할하는 단계를 거칠 때마다, 계산량이 기하급수적으로 줄어들기 때문에, 생각보다 풀이 시간이 짧습니다.

 

주의할 사항은, 큰 수를 연속해서 곱하게 되면 결과를 담은 변수의 표현 범위를 넘어섭니다.

그래서 문제도 정해진 값을 넘을 수 없도록 정해진 값의 나머지를 요구하고 있습니다.

 

다음과 같은 식으로 결과 값을 제한할 수 있습니다.

C = A*B의 경우 ( A, B, C, D는 정수 )

C mod D = A*B mod D = (A mod D * B mod D) mod D

 

이고, 이를 사용하면 모든 결과 값은 D를 넘을 수 없습니다.

typedef long long LTYPE;

LTYPE CalcExp(int a, int b, int c){	// a^b를 구하는 함수, c는 제한 값

    LTYPE val;

    if ( b == 1){	// 기저 조건
        val = a % c;
    }
    else if ( b % 2 ==1){   // 홀수인 경우
        val = a * CalcExp(a, b-1, c) % c;
    }
    else{

        int half = b / 2;	// 곱하는 횟수를 반으로 줄일 수 있다

        LTYPE hval = CalcExp(a, half, c);
        
        val = hval * hval % c;	// mod 연산을 통해, 숫자의 크기를 제한
    }

    return val;
}

단계마다 지수의 크기를 반으로 줄일 수 있습니다.

만약, 지수가 홀수인 경우 짝수 지수의 결과에 a값을 한 번 더 곱하는 식으로 해결할 수 있습니다.

 

 

소스 코드

#include <iostream>
using namespace std;

typedef long long LTYPE;

LTYPE CalcExp(int a, int b, int c){

    LTYPE val;

    if ( b == 1){
        val = a % c;
    }
    else if ( b % 2 ==1){
        val = a * CalcExp(a, b-1, c) % c;
    }
    else{

        int half = b / 2;

        LTYPE hval = CalcExp(a, half, c);
        
        val = hval * hval % c;
    }

    return val;
}

int main(){

    int A, B, C;
    cin >> A >> B >> C;

    int val = CalcExp(A, B, C);

    cout << val;

    return 0;
}