백준 14494번 다이나믹이 뭐예요? 자바로 풀어 본 짧은 글

14494번 다이나믹이 뭐예요?

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

14494번: 다이나믹이 뭐예요?

---

Comment

DP문제의 기초격 문제

DP는 기초라고해도 왜이리 생각하기 어려운지 모르겠다..

---

hint

dp배열의 저장값 : 해당 지점에 도달하는 경우의 수

점화식 : 우측, 하단, 우하단 세가지 경우의 수를 활용

---

Solution

DP의 기초격 문제라 그런가 DP를 조금 맛본 상태에서 접했더니 점화식이 생각났던 얼마안되는 문제

먼저 dp배열을 만들고 해당 dp배열의 상단(우측으로만 진행하는 경우의 수) 하단(아래로만 진행하는 경우의 수)의 값은 도달하는 방법이 한가지 뿐이다. 때문에 먼저 초기화해서 쭉 1로 채워준 후에 해당 값을 가지고 남은 dp배열 모두를 채워나가면 되는데, 점화식은 위에 hint에 적었던 우측, 하단, 우하단 을 받는 이전dp배열을 가져오면 된다.

즉, dp[i][j] = dp[i - 1][j] + dp[i][j-1] + dp[i-1][j-1]; 로 해결이 된다

그림예시

 

import java.io.*;
import java.util.*;
 
/**
 * dp 다차원배열 도달할 수 있는 경우의 수
 */
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int n, m;
 
        StringTokenizer st =new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        int[][] dp = new int[1001][1001];
 
        for(int i = 1; i <= n; i++){
            dp[i][1] = 1;
        }
 
        for(int i = 1; i <= m; i++){
            dp[1][i] = 1;
        }
        //값 초기화 끝
 
        for(int i = 2; i <= n; i++){
            for(int j = 2; j <= m; j++){
                dp[i][j] = (((dp[i-1][j] + dp[i][j-1]) % 1000000007) + dp[i-1][j-1]) % 1000000007;
            }
        }
 
        System.out.println(dp[n][m]);
        
    }
}