[백준/자바] 14494번: 다이나믹이 뭐예요?

문제

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

풀이

• →, ↓, ↘ 세 방향만 사용해서 한 번에 한 칸씩 이동
• (1, 1)에서 출발하여 (n, m)에 도착하는 경우의 수 출력

2차원 dp
굉장히 기본적인 문제입니다.
(1, 1)부터 시작하여 (i-1, j), (i, j-1), (i-1, j-1)의 값을 모두 더하며 (n, m)의 값을 출력하면 됩니다.

코드

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

public class Main {
	static int n, m;
	static long[][] dp;
	static final int MOD = 1000000007;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		dp = new long[n+1][m+1];
		dp[1][1] = 1; // 시작 지점 설정
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (i == 1 && j == 1) continue; // 시작 지점 제외
				dp[i][j] = (dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]) % MOD;
			}
		}
		
		System.out.println(dp[n][m]);
	}
}