백준 1629 곱셈(C++)

* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다

백준 1629 곱셈입니다

 

 

문제 해석

일단 이문제 같은경우는 문제만 봤을때는 매우 쉽게 느껴질수도있습니다

예제에 나온대로 10을 11번 곱해서 나온값을 12로 나눈 나머지를 출력하라고 나와있듯이 10의11승 나누기 12를 해서 나온 나머지를 출력하면됩니다

 

단순히 구현을 한다면 B만큼 반복문을 돌리면서 A를 계속 곱해주고 마지막에 C로 나눈 나머지를 출력하면 되는문제입니다

하지만 이렇게 문제풀면 시간초과 도 발생을하고 오버플로우도 같이 발생합니다

우선 시간초과 같은경우는 현재 입력되는 값에 가장 최대값은 약 21억입니다 하지만 시간 제한은 0.5초 이기 때문에 21억번의 반복문은 시간초과를 발생시킵니다

 

이러한 문제를 해결하기위해서는 반복문을 사용하지 않고 문제를 풀어야됩니다

문제를 푸는 방법은 예를 들어 2의64승을 계산을 해야된다고 했을때 2의64승을 분해 해봅니다

즉 2의64승 = 2의32승 * 2의32승이 되는것이고 다시 2의32승 = 2의16*2의16이 되고 2의1승이 나올때까지 재귀적으로 반반복을 해줍니다. 이때 분해한 부분은 한번만 계산해도 되기에 변수에 담아주고 변수*변수하여 연산 코스트를 줄일수있습니다

 

다음은 오버플로우 발생에 대한 부분인데 최대 범위로 계산을 해보면 21억 을 21억번 곱해야됩니다 즉 어떠한 자료형으로도 오버플로우가 발생합니다 이때 해결할수있는 방법은 mod 연산에 개념을 사용하는것입니다

(a+b) % c = (a%c) + (b%c) 와 같고 (a*b) % c = (a%c) * (b % c) 와 같습니다 이러한 개념을 사용하여

 

위에서 정의한 계산마다 c에 대한 mod연산을 계속해주면 오버플로우가 발생하지 않습니다

 

또한 만약에 2의5승 같이 홀수값이 들어온경우 2의5승은 2의 2승 * 2의2승 * 2의1승이기 때문에 2의1승이 남게됩니다

때문에 홀수인경우 2의1승에 대한 계산을 한번더 해주면됩니다

 

문제 풀이 순서

1. 우선 이문제같은경우는 int에 범위로는 풀수없기에 long 자료형을 사용합니다

2. long 자료형의 A,B,C 변수를 선언합니다

3. 계산을 나누기 위한 재귀함수를 선언합니다

4. 재귀함수는 무조건 기저사례가 있어야 되기때문에 b(target)이 1이되었을때 a%c를 한값을 리턴해줍니다

5. 이후 위에서 정의한대로 계산을 나누기 위한 변수를 선언하고 해당 변수들을 곱해준다음 c로 나눕니다

6. 이때 만약 나누는 값이 홀수라면 한번더 곱해줍니다

7. 이후 main함수에서 a,b,c를 입력받고 선언한 재귀함수를 호출해줍니다

 

작성코드

#include<bits/stdc++.h>
using namespace std;

//int 범위로는 풀수가없기에 long long 사용
typedef long long ll;

//long 자료형의 A,B,C변수 선언
ll a,b,c;

//계산을 나누기 위한 함수선언
ll go(ll num,ll target){

    //재귀함수 탈출을 위한 기저사례
    if(target == 1){
        return num % c;
    }

    //a를 8번 곱하는거는 a를 4번 곱한 두개를 곱한거랑 같기때문에 재귀함수를 사용한다
    ll temp = go(num, target / 2);
    ll ret = (temp * temp) % c;

    //만약 나누는값이 홀수라면 한번더 곱해준다(2의5승은 2의2승 * 2의2승 * 2의1승
    if(target % 2){
        ret = (ret * num) % c;
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    //a,b,c 입력 및 계산 결과 출력
    cin >> a >> b >> c;
    cout << go(a,b) << "\n";
    return 0;
}