leetcode 62. Unique Paths 풀이

문제 : int m 과 n 이 주어질때 m x n grid (0,0) 에서 출발해서 right, down으로만 이동하여 (m-1, n-1) 에 도달한다. 도달하는 유니크한 경우의 수를 반환하라

Follow up :

 

아이디어 : 이전에 풀었던 경로상의 비용을 최소화 하는 dp문제와 유사하다고 생각했다. 가로로만 가는 경우, 세로로만 가는 경우는 유니크 경로가 하나만 존재한다. 이 경우를 먼저 설정한 후. 나머지 경로에 대해서는 인접한 left, top 경로의 경우의 수 합으로 유니크 경로를 저장한다.

 

코드 :

 

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

 

학습 포인트 : 문제가 dp인지 아닌지 먼저 확인하여 어떻게 풀이를 전개할 것인지 고민하는 것이 필요하다. 만약에 이 문제를 탐색으로 생각해서 풀었다면 아마 시간 복잡도에서 문제가 발생했을 것이다.

 

출처 : leetcode.com/problems/unique-paths/