[백준 1629] 곱셈

문제

1629번: 곱셈

1629번: 곱셈

해결

시간초과

간단하게 for문으로 A를 B만큼 곱한다음 C로 나누어 값을 구할 수 있다. 하지만 이 문제의 입력값은 최대 2,147,483,647이고, 시간제한은 0.5초이다.

 

널널하게 2억번의 연산당 1초로 잡아도 10초 이상의 시간이 걸리게 되는 것을 알 수 있다. 따라서 B만큼 곱하는 방법은 사용할 수 없다.

오버플로우

최대 입력값이 2,147,483,647가 들어온다고 명시되어 있다. 이 값은 꽤 큰 값이기 때문에 큰 값이 들어온다면 연산시 오버플로우가 발생할 것이다.

지수 계산

이 문제는 오버플로우를 어떻게 해야할 지는 제시를 해 준 상태이다. 수가 너무 클 것을 알고 C로 나눈 나머지 값을 구하라는 말을 문제 자체에서 해주고 있다.

 

그렇다면 문제는 시간초과인데, 어떻게하면 시간복잡도를 줄일 수 있을까?

 

지수를 얼마나 쪼개어 계산할 수 있는지를 보면 된다.

A를 2, B를 64라고 해보자.

2를 64번 곱한다는 것을 2^64로 표현할 수 있다.

그렇다면 2^64 = 2^32 * 2^32와 같이 표현할 수 있다. 이것을 계속해서 나열해보자

 

2^32 = 2^16 * 2^16

2^16 = 2^8 * 2^8

2^8 = 2^4 * 2^4

2^4 = 2^2 * 2^2

2^2 = 2^1 * 2^1

 

이렇게 계산을 해 나가면 2를 64번 곱할 필요가 없다. 이미 구한 값을 다시 한번 곱해주면 된다.

그리고 연산되는 방식을 보면 재귀에 아주 적합하다는 것을 볼 수 있다.

코드

package 곱셈;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        long go = go(A, B, C);

        System.out.println(go);
    }

    static long go(long A, long B, long C) {

        if (B == 1) return A % C;

        long val = go(A, B/2, C);
        val = val * val % C;
        if (B%2==1) val = val * A % C;

        return val;
    }
}

• if (B == 1) return A % C; : Base condition을 정해 해당 조건에서 더이상 호출되지 않게 한다. 반환할 A는 지수가 1일 때의 값이다. 즉, 지수의 최소 값이다. 너무 큰 값을 반환하면 오버플로우가 발생하기 때문에 C로 나눈 나머지 값을 반환한다.
• long val = go(A, B/2, C); : 지수의 1/2에 해당하는 값을 연산한 결과를 반환 받는다.
• val = val * val % C; : 반으로 나눈 지수의 값을 구했으니 두 값을 곱한다.
• if (B%2==1) val = val * A % C; : 지수가 홀수였다면 지수를 한번 더 곱해줘야 한다. go() 메소드에 값을 넘길 때 2를 나눈 값을 넘겼다면 지수 1이 사라지는 것과 같기 때문이다.