[Leetcode/Python] Unique Paths

Top Interview Questions 의 Medium Collection에 있는 문제입니다.         
문제는 여기서 볼 수 있습니다.

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 * 109.

 

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

 

Constraints:

• 1 <= m, n <= 100

 

Code:

# 오른쪽이나 아래쪽으로만 이동가능
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        answer = 1 # 답 저장할 변수
        denominator = 1 # 중복조합 계산 시 나누는 수(=분모에 곱하는 수)
        #1 : factorial 계산(중복조합 이용해 경우의 수 계산)
        # m+n-1 : (m + n - 2) + 1 -> range 특성상 +1 해줌
        # numerator : 분자에 곱하는 수
        for numerator in range(m, m+n-1):
            answer *= numerator
            answer //= denominator
            denominator += 1
            
        return answer

위의 for문은 중복조합 계산 과정입니다.

 

위 예시의 이미지처럼 m=3, n=7일 경우 구체적 경로와 상관없이 무조건 아래로 2(m-1)번, 오른쪽으로 6(7-1)번 움직이게 됩니다.

총 8번 중에 아래로 2번 움직이는 중복조합을 계산하는 것과 다름 없으므로 (8*7)/(2*1) = 28 입니다.