•
문제 링크 : 
LeetCodeUnique Paths - LeetCode
•
문제 설명 : 오른쪽, 아래 두 방향으로만 이동 가능할 때 제공된 좌표에 도달할 수 있는 방법이 몇가지인지 반환한다.
•
풀이 방법
◦
처음에는 DFS로 탐색하면서, 전역변수에 카운트를 증가시키는 방향으로 진행했다.
▪
이 방법은 조금만 목표 좌표가 멀어도 금방 시간 초과가 발생하였다.
◦
결국에는, 일일히 탐색은 어렵다고 판단하고 Dynamic Programming(DP)를 사용해야 할 것 같았다.
▪
이를 위해, 이전 좌표를 사용하여 현재 좌표를 구하는 점화식을 간단히 세웠고 이를 적용하였다.
•
시간복잡도 : → 제공된 목표 좌표 m, n을 사용한 움직일 수 있는 면적만큼만 시간이 걸린다.
•
성공 코드
class Solution:
point_info = {(1, 1): 1}
def uniquePaths(self, m: int, n: int) -> int:
self.result = 0
def path_count(x, y):
if self.point_info.get((x, y)):
return self.point_info[(x, y)]
elif x == 1:
self.point_info[(x, y)] = path_count(x, y - 1)
elif y == 1:
self.point_info[(x, y)] = path_count(x - 1, y)
else:
self.point_info[(x, y)] = path_count(x - 1, y) + path_count(x, y - 1)
return self.point_info[(x, y)]
return path_count(n, m)
Python
복사