Q10164. 격자상의 격로

경로를 저장하며 나아가는 로직

k[i][j] = k[i-1][j] + k[i][j-1] 입니다.

동그라미가 없는 경우 (K=0 일때)와 동그라미가 있는 경우를 나누어서 구현했습니다.

(이해하기 쉽도록, 처음 생각한 대로 구현했어요)

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q10164 { static int[][] dp; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken()); dp = new int[N+1][M+1]; if (K == 0) { for (int i = 1; i <= M; i++) { dp[1][i] = 1; } for (int i = 1; i <= N; i++) { dp[i][1] = 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]; } } } else { int y = K / M; int x = K % M; if (x > 0) { y += 1; } else if (x == 0) { x = M; } for (int i = 1; i <= x; i++) { dp[1][i] = 1; } for (int i = 1; i <= y; i++) { dp[i][1] = 1; } for (int i = 2; i <= y; i++) { for (int j = 2; j <= x; j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } for (int j = x+1; j <= M; j++) { dp[y][j] = dp[y][j-1]; } for (int i = y+1; i <= N; i++) { for (int j = x; j <= M; j++) { if (y > 1) { } dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } } System.out.println(dp[N][M]); } }