[백준]1629 - 곱셈 문제 풀이(Java,자바)

문제

1629번: 곱셈

들어가며

이 문제를 처음 봤을 때, dp로 하면 될 것 같아 했다가 바로 메모리 초과가 떴습니다.

그렇습니다.

이 문제는 바로 수학과 분할정복에 관한 문제입니다.

풀이

package solved.ac.class4;

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

public class 백준1629_곱셈 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        long c = Long.parseLong(st.nextToken());

        System.out.println(modularExponentiation(a, b, c));

    }

    public static long modularExponentiation(long a, long b, long c) {
        if (b == 0) {
            return 1; 
        }

        long half = modularExponentiation(a, b / 2, c);
        long result = (half * half) % c;

        if (b % 2 == 1) { // b가 홀수인 경우
            result = (result * a) % c;
        }

        return result;
    }
}

 

나머지 연산을 mod 연산이라고 합니다.

mod 연산을 완성시킬 점화식이 필요합니다.

b가 홀수와 짝수인지에 따라 잘 구분해야 합니다.

먼저 분할 정복을 보실 땐, 짝수부터 보면 쉽게 찾을 수 있습니다.

짝수는 반으로 분할이 가능하거든요.

 

결과만 빠르게 보면

a^10 mod c =((a^5 mod c)^2) mod c.

위와 같은 점화식을 도출할 수 있습니다.

 

그러면 홀수는 어떻게 하면 될까요?

따로 때서 계산해주면 됩니다.

여기서 mod를 중간 중간 계속 넣는 이유는 문제에도 나와있다 싶이 변수의 최대값을 넘지 않게 하기 위해서입니다.