-
https://www.acmicpc.net/problem/1520
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지
www.acmicpc.net
사실 조금 전형적인 DP라고 볼수도 있겠다.
이런것들을 연습하면서 DP유형이 DP의 기본이다.
하향식으로 문제를 풀었고, 재귀 연습이 되는 문제
그리고 한가지 더 언급하고싶은것이 MEMOIZATION이다.
메모이제이션이 필요한 이유에 대해서는 검색하면 나보다 더 설명을 잘해주는 분들이 많겠지만
간단히 언급하자면, 중복되는 계산을 하지 않기 위해서이다.
재귀에서 모든 노드를 방문해서 모든계산을 하게된다면 시간복잡도는 기하급수적으로 증가하게된다.
메모이제이션을 통해 이미 캐시에 계산되있는것들을 계산하지 않는다면 굉장히 효율적인 계산을할수있고
하향식에서 가장 위험한 부분인 메모리 관리에있어서도 바로 Return 을 시켜주기 떄문에
메모리도 효율적으로 쓸수 있는 부분이다.