[백준 - 1520] 내리막 길

출발점에서 목적지까지 내려가는 경로 수를 바로 세도 되지만, 구현에서는 목적지에서 시작해 더 높은 칸으로 거꾸로 올라갔다. 그러면 현재 칸에 도착하는 내리막 경로 수는, 인접한 더 높은 칸들의 경로 수를 더한 값이 된다.

ways(y, x) = Σ ways(higher adjacent cell)

-1은 아직 계산하지 않은 상태, 0 이상은 이미 계산한 경로 수로 사용했다. 높이는 항상 감소하는 방향으로만 이동하므로 순환이 생기지 않아 DFS와 메모이제이션을 함께 쓸 수 있었다.

문제: 1520 내리막 길 · 코드: GitHub에서 보기