'등굣길' 태그의 글 목록

처음에 dfs로 풀려고 했다가 계속 시간초과가 나서, 분류대로 dp로 풀어야겠다고 생각했다. 나는 dp로 문제를 풀 때, 가장 먼저 해야할 점은 어떤 정보를 저장해서 사용할 것인가 라고 생각한다. 그래서 나는 각 칸마다 그 칸까지 올 수 있는 최소 경로의 수를 저장하기로 했다. 초등학교 때 풀던 최단경로의 개수 찾기 문제랑 동일하다. (x, y)까지 오는 최단경로 수는 (x-1, y)까지 최단 경로로 온 경우의 수 + (x, y-1)까지 최단 경로로 온 경우의 수 이다. (x-1, y)와 (x,y-1) 중 범위를 벗어난 좌표 이거나 웅덩이 좌표이면 더해주지 않는다. dx = [-1, 0] dy = [0, -1] count = 0 def solution(m, n, puddles): global count ..