[백준/10164] 격자상의 경로 - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 실버2
출처 : 백준 - 격자상의 경로

🦧 문제 풀이 접근

DP 알고리즘을 사용해서 풀이한다.
K가 0인 경우와 0이 아닌 경우로 나눠서 계산한다.

K가 0일 경우 0,0부터 N-1,M-1까지의 경우를 DP로 계산한다.
K가 0이 아닐 경우, 0,0부터 K가 있는 위치까지의 경우와 K가 있는 위치부터 N-1, M-1까지의 경우를 각각 DP로 계산해 곱한다.

💻 code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        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());
        if(K==0)
            System.out.println(countRoad(N,M));
        else
            System.out.println(countRoad((K-1)/M+1, (K%M==0)?M:K%M) * countRoad(N-K/M,M- ((K%M==0)?M:K%M)+1));
    }
    static int countRoad(int n, int m) {
        int dp[][] = new int[n][m];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(i==0 && j==0)
                    dp[i][j]=1;
                else if(i==0)
                    dp[i][j] = dp[i][j-1];
                else if(j==0)
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        return dp[n-1][m-1];
    }
}

🥇 결과

🎓 느낀점

DP 알고리즘은 간단하지만 오히려 범위를 지정하는 부분에서 많은 에러가 발생했다.