[Baekjoon] 1629: 곱셈

문제

a^b % c를 구하는 문제이다.

 

풀이

내 풀이

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

public class Q1629 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        long a = Long.parseLong(input[0]);
        long b = Long.parseLong(input[1]);
        long c = Long.parseLong(input[2]);

        System.out.println(getMul(a, b, c));
    }

    public static long getMul(long num, long pow, long mod) {
        if (pow == 1) {
            return num % mod;
        }

        long value = getMul(num, pow / 2, mod);
        if (pow % 2 == 0) {
            return (value * value) % mod;
        }
        return (((value * value) % mod) * (num % mod)) % mod;
    }
}

이 문제를 풀이하기 전에 먼저 값의 범위를 보면 2147483647 이하의 자연수임을 확인할 수 있다.

즉 그냥 계속 곱한 후 나머지를 구하면 overflow가 난다는 것은 자명하다.

 

때문에 모듈러 연산을 통해 다음을 구할 수 있다.

(a × b) mod n ≡ ((a mod n) × (b mod n)) mod n

 

하지만 이를 선형 탐색을 통해 해결하면 시간초과가 나게된다.

즉 O(n)으로는 안풀리는 문제인 것이다.

때문에 이를 풀기 위해선, 분할정복을 이용한 거듭제곱을 이용해야한다.

 

그 풀이는 위와 같은데, 지수를 계속 2로 나누면서 들어간 다음 나올때 곱해주는 형식이다.

나왔을 때 지수가 짝수이면 나온 값을 제곱해주고, 홀수이면 제곱한 수에 원래 값을 한 번 더 곱해주면 해결된다.

 

이를 점화식으로 표현하면 다음과 같다.

 

회고

분할정복을 통해 문제를 해결하는 방법이 떠오르지 않아, 위 내용을 공부해서 풀었다.

 

분할정복에 대한 지식과 경험이 부족한 것 같다. 이에 대해 좀 더 공부해봐야겠다.