문제 www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 다이나믹 프로그래밍과 DFS가 결합된 문제이다. 메모이제이션으로 값을 재사용하는 최적화를 하기 위해서는 어떤 부분에서 중복된 계산이 이루어지는지 확인해야 한다. 해당 문제에서 DFS로 시작점에서 더 작은 수로 재귀 호출을 한다고 해보자. 문제에서 주어진 예제는 아래와 같다. 출발점인 50에서 45로 분기하였다고 가정하면 32에서 20이나 30으로 진행하는 두 가지 경로로 나뉜다. 해당 호출들에서는 아래와 ..