리트코드 - 62. Unique Paths

리트코드 - 62. Unique Paths

세로 m 가로 n인 사각 격자의 왼쪽위 꼭지점에서 오른쪽아래 꼭지점까지 잇는 최단경로의 수를 구하는 문제입니다.
경로를 이동방향에 따라 아래쪽과 오른쪽으로 표현해보겠습니다.

ex) m = 2, n = 2
경로 1 : 아래쪽 -> 오른쪽
경로 2 : 오른쪽 -> 아래쪽
두 가지 경로가 있으므로 2를 return하면 됩니다.

이 문제는 결국 m - 1개의 아래쪽과 n - 1개의 오른쪽을 배치하는 경우의 수를 구하는 문제입니다.
이는 m + n - 2 개의 자리에서 n - 1 개의 자리를 뽑아 오른쪽을 넣는 경우와 같습니다. (Combination을 구하면 됩니다)
overflow를 방지하기 위해 중간중간 나눠줬습니다.

class Solution {
    public int uniquePaths(int m, int n) {
        int ans = 1;
        long mom = 1;
        long son = 1;

        long large = Math.max(m, n);
        long small = Math.min(m, n);

        for (int i = 0; i < small - 1; i++) {
            long curMom = small - 1 - i;
            long curSon = large + small - 2 - i;

            son *= curSon;

            if (son % curMom == 0) {
                son /= curMom;
            } else {
                mom *= curMom;
            }
        }   

        son /= mom;
        return Long.valueOf(son).intValue();
    }
}