[백준][DP] 1520번 내리막 길

문제

각 칸의 높이가 적인 지도가 주어질 때 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1520)

풀이

처음에 문제를 꼼꼼히 읽지 않고 오른쪽으로만, 아래쪽으로만 이동할 수 있도록 dp를 구현했었습니다. 그런데 문제에서 주어진 조건은 낮은 높이로 이동할 수 있는 모든 경우를 알아내야하기 때문에 지도상으로는 더 아래있는 칸에서 위로도 이동할 수 있는 경로가 있었습니다. 정렬을 써서 해야한다는 힌트를 얻었지만 어떻게 활용할지 생각이 나지 않았는데 큰 칸 먼저 dp의 값을 계산하면 4방향에서 오는 모든 경우를 구할 수 있겠다는 생각이 들었습니다. 

55 99 49 48 47

54 99 50 99 46

53 52 51 99 45

이와 같은 케이스가 주어진다면 세번째 줄의 51에서 시작해서 51->50->49->48->47->46->45 와 같이 제일 오른쪽 아래를 갈 수 있습니다. 이러한 경로들을 모두 고려해주기 위해서는 무조건 높이가 높은 칸의 dp값이 계산되어 있어야 그 다음칸을 계산하는데 문제가 생기지 않습니다. 저는 그래서 처음 입력을 받을 때 높이와 함께 좌표를 priority queue에 넣어준 다음 큰 값을 뽑아내면서 그 칸을 기준으로 4방향에서 올 수 있는 경우들을 다 더해주도록 했습니다.

코드

https://github.com/kswim/Algorithm/blob/master/DP/1520.cpp