[백준] 10164번. 격자 상의 경로(JAVA)

문제

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

---

풀이(15분)

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

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) { // o가 없는 경우
            System.out.println(comb(n + m - 2, Math.min(n - 1, m - 1)));
            return;
        }

        int row = (k - 1) / m; // 1-based index -> 0-based index 변환
        int col = (k - 1) % m;

        long firstCase = comb(row + col, Math.min(row, col));
        long secondCase = comb((n - row - 1) + (m - col - 1), Math.min(n - row - 1, m - col - 1));

        System.out.println(firstCase * secondCase);
    }

    private static long comb(int n, int r) {
        long result = 1;
        for (int i = 0; i < r; i++) {
            result *= (n - i);
            result /= (i + 1);
        }
        return result;
    }
}

---

문제 풀이 전략

 

경유해야 하는 지점이 0개 or 1개로 지정되어 있기에 고등학교 시절의 경로 찾기 문제를 떠올렸다. 

유사한 문제에 대한 접근 https://to-travel-coding.tistory.com/280 이 있으니 경로 찾기 문제에 대해 익숙하지 않다면 참고해 보자.

 

다만, 여기서 사용된 방법은 단순한 숫자 채우기(dp)가 아닌 조합론적인 방법이다.

예를 들어, (0,0)에서 (3,3)으로 가야 한다면 우리는 →로 3칸, ↑로 3칸을 진행해야 한다는 것을 알고 있다. 그렇다면 

→→→↑↑↑를 통해 몇 가지 경우의 수가 나오냐는 것이다.

이때, 중복된 순열이기 때문에 6!/3! 3! 을 해주면 된다.

즉. 좌표만 알면 단순한 계산을 통해 해결할 수 있는 것이다.

 

 

따라서, 문제 해결은 다음과 같이 진행되었다.

 

1. 경유해야 하는 지점이 있는지 없는지를 검사한다.

1-1. 없다면 (n, m)의 좌표를 이용하여 조합을 계산한다.

 

2-1. 있다면 경유 전의 경로의 수를 구한다.

2-2. 경유 후의 경로의 수를 구한다.

2-3. 두 경로의 수를 곱한다.