[Algorithm][LeetCode][Medium][Python] 62. Unique Paths

문제는 여기에서 볼 수 있다.

 

 

고등학교 시절 자주 풀던 유형의 수학 문제와 똑같은데,

 

m행 n열의 그리드가 있을 때

 

(0, 0)에 위치한 로봇이 (m-1, n-1)까지 도달하는 경로의 수를 구하는 문제이다.

 

---

 

풀이 1

보자마자 수험생 시절 지긋지긋하게 풀었던 수학 문제와 똑같아서

 

바로 공식을 적용해서 풀어봤다.

 

 

m행 n열의 행렬이 있을 때,

 

유니크한 경로의 수를 구하는 공식은 Combination을 이용하는 것이다.

 

보통 (m+n-2)C(n-1) 공식으로 쉽게 구할 수 있다.

 

 

내가 수험생 시절 다녔던 수학 학원 원장님이 정말 천재여서

 

이러한 특정 유형의 문제에서의 공식들을 굉장히 매끄럽게 유도하고 알려주셨었다.

 

 

하고 싶은 말은 위 공식의 원리는 잘 기억이 안 남.

 

 

하여튼 완성된 내 코드는 아래와 같으며 나름 좋은 성능을 보여주었다.

 

import math

class Solution:
	def uniquePaths(self, m: int, n: int) -> int:
    	return math.comb(m+n-2, n-1)

 

 

풀이 2

discussion에서 찾아낸 Dynamic Programming 방법이다.

 

사실상 위 풀이 1과 원리는 동일하기 때문에 코드가 쉽게 이해 간다.

 

 

코드를 보기 전 product라는 함수에 대해 아는 것이 좋다(참고 사이트).

 

for 문을 돌면서 dp라는 배열에 경로의 수를 계속 누적해나간다.

 

 

성능은 풀이 1보다 좀 더 좋았다.

 

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

 

 

끝!