[백준] No.1520 - 내리막 길 (C++)

문제

www.acmicpc.net/problem/1520

1520번: 내리막 길

 

풀이

다이나믹 프로그래밍과 DFS가 결합된 문제이다.

 

메모이제이션으로 값을 재사용하는 최적화를 하기 위해서는 어떤 부분에서 중복된 계산이 이루어지는지 확인해야 한다.

해당 문제에서 DFS로 시작점에서 더 작은 수로 재귀 호출을 한다고 해보자.

 

문제에서 주어진 예제는 아래와 같다.

출발점인 50에서 45로 분기하였다고 가정하면 32에서 20이나 30으로 진행하는 두 가지 경로로 나뉜다.

해당 호출들에서는 아래와 같이 노란색이 칠해진 경로가 동일하게 사용된다. 

따라서 우리는 이미 탐색이 진행된 경로의 값을 다시 사용한다면 중복의 계산을 없애고 최적화할 수 있다는 것을 알 수 있다.

 

route_count[500][500] 배열을 통해 해당 위치가 가지는 경로의 가지 수를 저장하는 DFS를 구현하자.

 

해당 위치 (r,c)에서 인접 값들 중에 더 작은 값이 있다면 해당 위치를 재귀 호출하여 해당 위치가 가지는 경로 수들을 모두 합하여 route_count[r][c]에 기록해 둔 후에 반환한다.

 

코드