[백준] 1629번 - 곱셈

 

1629번: 곱셈

 

 

문제가 이렇게 짧은 것은 흔하지 않다. 입력으로 주어지는 자연수 A를 B번 곱한 수를 구하면 되는 간단해 보이는 문제이지만 A, B가 2,147,483,647 이하의 자연수라는 것과 시간 제한이 0.5초에 불과한 것에 유의해야 한다.

 

입력으로 주어지는 수의 최댓값이 굉장히 커서 자연수이지만 자연수 같지 않은 느낌마저 든다.

 

 

 

어찌됐든, 문제를 푸는데에는 크게 세부분을 주의하면 된다.

 

 

i) 만약 B가 가질 수 있는 크기의 최댓값이라면, A를 B번 곱할 경우 약 21억번의 연산을 하게 되어 주어진 시간 내에 답을 얻지 못할 것이다. 따라서 분할 정복으로 연산의 중복을 줄인다.

수학에서의 지수는 특정 수를 몇 번이나 거듭제곱 했는지를 의미한다. 지수법칙에 의하면 

A^(a+b) = A^a * A^b 가 성립한다. 

이를 문제에 적용하면, B를 2로 나누어 떨어진다면 A를 B/2번 거듭제곱한 결과를 제곱하여 C로 나눈 것을 반환하고, B가 2로 나누어 떨어지지 않는다면 A를  B/2번 거듭제곱한 결과에 A를 한번 더 곱한것을 C로 나누어 반환한다.

static long DAC (int num, int divisor, int exp) {
        
    if (exp == 1) return num % divisor;

    long temp = DAC(num, divisor, exp / 2);


    if (exp % 2 == 0) return temp*temp % divisor;

    else return (temp*temp%divisor) * num % divisor;
}

 

ii) 앞서 말했듯이 입력으로 주어지는 자연수의 최댓값은 int형의 최댓값과 같다. 따라서 곱셈 연산에 대한 결과는 일시적으로 int형을 초과할 수 있으므로 long 타입에 담아준다. 

 

iii) 모듈러 산술을 적용한다. 모듈러 산술이란

(A + B) / C = (A / C + B / C) / C

(A * B) / C = (A / C * B / C) / C

위와 같이 괄호를 먼저 계산하고나서 C로 나누는 결과와 괄호의 각 숫자를 C로 나눈 것을 다시 C로 나눈 결과는 동일하다는 것이다.

 

 

처음 이 문제를 해결할 때 삼고초려만에 '맞았습니다'를 받았는데 모듈러 산술을 일부에만 적용해서 틀렸습니다가 떴었다. 중간 연산 결과를 long 타입으로 두었다고 막연히 통과하겠거니 제출했었는데 위 메서드에서 temp * temp와 같이 자료형의 범위를 벗어날 수 있는 연산이 존재하는지 주의해야한다.

 

 

 

전체코드

import java.util.*;

public class Main {
    
    public static void main (String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        
        System.out.println(DAC(A, C, B));
        
        sc.close();
    }
    
    static long DAC (int num, int divisor, int exp) {
        
        if (exp == 1) return num % divisor;
        
        long temp = DAC(num, divisor, exp / 2);
        
        
        if (exp % 2 == 0) return temp*temp % divisor;
        
        else return (temp*temp%divisor) * num % divisor;
    }
}