Medium - Unique Paths

https://leetcode.com/problems/unique-paths/description/

Unique Paths - LeetCode

문제 설명

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10 ** 9.

 

Constraints:

• 1 <= m, n <= 100

예시

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

풀이

from functools import cache

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        @cache
        def factorial(x: int) -> int:
            if x <= 1:
                return 1
            else:
                return factorial(x-1) * x

        return int(factorial(m+n-2) / factorial(m-1) / factorial(n-1))

수학 시간에 봤던 문제 st.

왼쪽 상단의 점에서 오른쪽 하단의 점까지 가는 최단 거리는 m-1 번의 Down 과 n-1 번의 Right의 중복 없는 조합의 수와 같다.

편의상 x = m-1, y = n-1이라 하면, 나올 수 있는 모든 경우의 수 (중복 포함)은 (x + y)! 이 된다.

여기서 같은 분류는 중복이 있으므로 (x1x2x3 은 x3x2x1, x3x1x2, x2x3x1, x2x1x3m x1x3x2 자신을 포함하여 x!만큼 중복이 생긴다.) x!와 y!의 곱으로 모든 경우의 수를 나눠준 값이 정답이 된다.

 

또한 여기서 factorial은 같은 값을 반복적으로 연산하게 되므로 (factorial(5) == factorial(4) * 5 == factorial(3) * 4 * 5 처럼) cache를 사용해서 computation을 줄여준다.