[LeetCode] 62 - Unique Paths

문제

• 링크: https://leetcode.com/problems/unique-paths
• 난이도: Medium
• 태그: 수학, 다이내믹 프로그래밍, 조합
• 결과: Time: 0 ms (100.00%), Space: 7.88 MB (92.31%)

풀이

조합을 이용한 풀이

class Solution {
public:
    int uniquePaths(int m, int n) {
        int k = min(m - 1, n - 1);
        return combination(m + n - 2, k);
    }

    int combination(int n, int k)
    {
        long long res = 1;
        for (int i = 1; i <= k; ++i)
        {
            res = res * (n - i + 1) / i;
        }

        return res;
    }
};

아래로 이동을 $D$, 오른쪽으로 이동을 $R$이라고 하자. 경로의 수는 $m-1$개의 $D$와 $n-1$개의 $R$을 일렬로 배열하는 경우의 수와 같다(같은 것이 있는 순열). 그러므로 다음과 같이 구할 수 있다.

\[\frac{(m+n-2!)}{(m-1)!(n-1)!}\]

다르게 표현하자면, $m+n-2$번의 이동 중 $m-1$개의 $D$의 위치를 선택하는 경우의 수와 같다(조합).

\[C(m+n-2,m-1)\]

이 때, $C(n,k)=C(n,n-k)$이므로 std::min으로 k를 구해 조합을 구하면 된다.

다이내믹 프로그래밍 풀이

class Solution {
public:
    int uniquePaths(int m, int n) 
    {
        vector<vector<int>> d(m, vector<int>(n, 1));
        for (int i = 1; i < m; ++i) 
        {
            for (int j = 1; j < n; ++j) 
            {
                d[i][j] = d[i - 1][j] + d[i][j - 1];
            }
        }

        return d[m - 1][n - 1];
    }
};

d[i][j] = i * j 그리드에서 경로의 수라고 하자. 가장 먼저 첫 번째 행과 열은 1로 초기화할 수 있다. 그리고 나머지 칸을 순회하면서 d[i][j] = d[i - 1][j] + d[i][j - 1]로 채울 수 있다.

이는 로봇이 오른쪽 또는 아래쪽으로만 움직일 수 있기 때문이다. i * j 크기의 그리드에서 도착지점으로 가는 경우의 수는 한칸 위에서 오는 경우의 수 + 한칸 왼쪽에서 오는 경우의 수이기 때문이다.

배운 점과 후기

뭔가 함정이 있는 건가 싶었는데 그냥 바로 조합으로 풀렸다. DP 풀이는 Editorial을 참고했다.

이 포스트는 달레 스터디(7주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.