LeetCode 62(Unique Paths, Python)

1. 문제 링크

• Unique Paths - LeetCode

Unique Paths - LeetCode

2. 문제 설명

• 고등학교 경우의 수에서 자주 보던 문제.
• 직사각형 경로에서 왼쪽 위에서 시작해서 오른쪽 아래로 갈 때 최단 경로의 개수를 묻는 문제.
• 예시) 아래 그림에서 오른쪽으로 6칸, 아래로 2칸 이동할 때 가능한 최단 경로의 수는 28가지. 

3. 처음 풀이

• 오른쪽으로 6칸, 아래로 2칸 이동할 때 최단 거리로 이동하는 방법의 수. 8개의 칸에 아래 화살표 2개, 오른쪽 화살표 6개를 채운다고 생각하고, 8개 중 아래 화살표 넣을 곳 2개를 고르면 8C2를 계산하면 된다.
• 마찬가지로 m, n이 주어지면 오른쪽으로 m-1칸, 아래로 n-1칸 가기 때문에 (m+n-2)C(n-1)을 계산하면 됨. 
• 이는 간단한 수학인데 분자에는 (m+n-2)부터 1씩 줄이면서 n-1개를 곱하고 분모에는 (n-1)!을 곱하면 됨. 

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        up = 1
        down = 1

        for i in range(m+n-2, m-1, -1): #분자
            up *= i
        for i in range(n-1, 0, -1): #분모
            down *= i

        return int(up/down)

4. 다른 풀이

• 이 또한 고등학교 경우의 수를 풀 때 많이 하던 방법인데
• 어떤 칸에 오려면 그 위에서 내려오거나 왼쪽에서 오는 방법 뿐이므로
• 어떤 칸에 오는 경우의 수는 바로 위 칸에 오는 방법의 수와 바로 왼쪽 칸에 오는 방법을 더하면 된다.
• 물론 가장 윗 줄과 가장 왼쪽 줄의 칸에 오는 방법은 모두 1이다.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for i in range(m)]
        for i in range(m): dp[i][n-1] = 1
        for i in range(n): dp[m-1][i] = 1

        for i in range(m-2, -1, -1):
            for j in range(n-2, -1, -1):
                dp[i][j] = dp[i+1][j] + dp[i][j+1]
        return dp[0][0]

5. 배운 점

• 수학은 코딩에 자주 쓰인다. 수학적 사고는 코딩에 매우 유용하다.