백준 10164번: 격자상의 경로

문제 설명

• https://www.acmicpc.net/problem/10164
• (1,1)에서 특정 위치를 거쳐 (N,M)으로 도달할 수 있는 경우의 수를 구하는 문제입니다.
  • 오른쪽 또는 아래로만 이동 가능합니다.

접근법

• K번째 수를 거쳐가야 하기 때문에 (1,1)에서 K까지 먼저 이동한 뒤 K에서 (N,M)으로 이동합니다.
• 특정 위치 (i,j)에 도달할려면 반드시 (i-1,j)에서 오거나 (i,j-1)에서 와야합니다.
  • dp[i][j] = dp[i-1][j] + dp[i][j-1]

정답

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

public class Main {
	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());
		// K번째 수의 좌표
		int r = (K==0)?0:(K-1)/M;
		int c = (K==0)?0:(K-1)%M;
		
		int[][] dp = new int[N+1][M+1];
		dp[1][1] = 1; // 시작위치
		
		// K번째 수까지 가는 경우의 수
		for (int i = 1; i <= r+1; i++) {
			for (int j = 1; j <= c+1; j++) {
				dp[i][j] += dp[i-1][j] + dp[i][j-1];
			}
		}
		// K번째 수에서 목적지까지 가는 경우의 수
		for (int i = r+1; i <= N; i++) {
			for (int j = c+1; j <= M; j++) {
				if(i == r+1 && j == c+1) continue; // 다시 출발하는 위치
				dp[i][j]+=dp[i-1][j] + dp[i][j-1];
			}
		}
		System.out.println(dp[N][M]);
		
	}	

}