[백준] 14494 다이나믹이 뭐예요? - 동적계획법(Dynamic Programming, DP) JAVA

https://www.acmicpc.net/problem/14494

코드설명

동적계획법(Dynamic Programming, DP) 를 활용합니다.

 

문제에서 유의해야할점입니다.

첫번째는, 중간 계산 과정에서의 오버플로우가 발생합니다. MOD 연산을 매 단계마다 수행하더라도, 덧셈을 수행하기 전의 중간 결과가 int의 범위를 초과할 수 있습니다. 

이 문제의 경우 아래와 같이 3개의 함수로 이루어져있기에 최대 10억씩 3개가 더해지면 중간과정에서 오버플로우가 발생합니다. 만약 두개만 더해졌다면 최대 20억이므로 오버플로우가 발생하지 않습니다.

ret += ( func(r, c + 1) % MOD + func(r + 1, c)% MOD + func(r + 1, c + 1) % MOD ) % MOD;

그러므로 long 자료형을 사용합니다.

 

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static int N, T, K, M, L;
    private static int[] arr;
    private static int answer = 0;
    private static long[][] cache = new long[1001][1001];
    private static PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=0; i<1001;i++) {
			Arrays.fill(cache[i], -1);
		}
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		System.out.println(func(1, 1));
    }
    
    private static final int MOD = 1000000007;
    private static long func(int r, int c) {
    	if(r == N && c == M) return 1;
    	if(r > N || c > M) return 0;
    	
    	if(cache[r][c] != -1) return cache[r][c];
    	long ret = 0;
    	ret += ( func(r, c + 1) % MOD + func(r + 1, c)% MOD + func(r + 1, c + 1) % MOD ) % MOD;
    	return cache[r][c] = ret; 
    }
}