백준 1629 - 곱셈

Java

1629 번 - 곱셈

문제

접근 방법

분할 정복과 modular의 특징을 사용하여 해결하였다.

한번 방문한 지수면 dp를 통해 값을 저장해 놓는다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m;
	static long result;
	static int a,b,c;
	static long[] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	
    	a = stoi(stk.nextToken());
    	b = stoi(stk.nextToken());
    	c = stoi(stk.nextToken());
    	
    	dp = new long[10000001];
    	
    	Arrays.fill(dp, -1);
    	result = recur(a,b,c);
    	System.out.println(result);
    	br.close();
	}
	
	private static long recur(int num, int exp, int mod) {
		if(exp <= 10000000 && dp[exp] != -1) {
			return dp[exp];
		}
		
		if(exp == 1) {
			return num % mod;
		}
		else if(exp == 2) {
			// 주의! int * int => int 초과
			// long * int => long
			return ((long)(num % mod) * (num % mod)) % mod;
		}
		
		int fir, sec;
		fir = exp / 2;
		sec = exp / 2;
		if(exp % 2 == 1)
			sec++;
		
		long rst = ((recur(num, fir, mod) % mod) * (recur(num, sec, mod) % mod)) % mod;
		if(exp <= 10000000)
			dp[exp] = rst;
		return rst;
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점