[백준 10164] 격자상의 경로

 

기존에 이런 문제를 풀어본 적이 있어서 당연하다는 듯이 DP로 풀었는데, 동그라미가 표시된 칸이 없는 경우가 있다는게 변수였다.

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

public class 격자상의경로 {
	static int N, M, K;
	static int[][] map;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		map = new int[N+1][M+1];
		
		int num = 1;
		int r = 0;
		int c = 0;
		if(K==0) {
			map[1][1] = 1;
			for(int i = 1; i <= N; i++) {
				for(int j = 1; j <= M; j++) {
					if(i==1 && j==1) continue;
					map[i][j] = map[i][j-1] + map[i-1][j];
				}
			}
			System.out.println(map[N][M]);
		}else {
			for(int i = 1; i < N+1; i++) {
				for(int j = 1; j < M+1; j++) {
					if(num==K) {
						r = i;
						c = j;
					}
					num++;
				}
			}			
			//동그라미까지의 경로
			map[1][1] = 1;
			for(int i = 1; i <= r; i++) {
				for(int j = 1; j <= c; j++) {
					if(i==1 && j==1) continue;
					map[i][j] = map[i][j-1] + map[i-1][j];
				}
			}
			for(int i = r; i <= N; i++) {
				for(int j = c; j <= M; j++) {
					if(i==1 && j==1) continue;
					map[i][j] = map[i][j-1] + map[i-1][j];
				}
			}
			System.out.println(map[N][M]);
		}
		
	}
}

 

동그라미가 표시된 경우와 동그라미가 없는 경우를 나누어서 DP로 풀었다.

 

하지만 다른 사람들 코드나 GPT에게 물어본 결과, 조합을 사용해서 동그라미까지 가는 경우의 수, 목적지까지 가는 경우의수를 각각 구해서 곱하는 경우가 더 효율적인 코드라고 한다.

 

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

public class Main {
    static int N, M, K;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        if (K == 0) {
            System.out.println(combination(N + M - 2, N - 1));
        } else {
            // Find (r, c) of K
            int r = (K - 1) / M + 1;
            int c = (K - 1) % M + 1;
            int path1 = combination(r + c - 2, r - 1); // Paths to K
            int path2 = combination((N - r) + (M - c), N - r); // Paths from K to (N, M)
            System.out.println(path1 * path2);
        }
    }

    // Combination nCr calculation
    static int combination(int n, int r) {
        if (r == 0 || n == r) return 1;
        r = Math.min(r, n - r);
        int result = 1;
        for (int i = 0; i < r; i++) {
            result *= (n - i);
            result /= (i + 1);
        }
        return result;
    }
}