boj_1520_내리막 길

https://www.acmicpc.net/problem/1520 <풀이> 처음 풀어보는 그래프 + DP 문제였다 (1,1) -> (M,N) 까지의 경로의 개수를 구하는 문제여서 완전탐색을 돌리기위해 dfs로 탐색해야했다. 그러면 어디서 반복되는 계산을 줄일 수 있을까?

위 예제는 서로 다른 두 경로이지만, "20"에 도착한 후로는 같은 경로로 진행된다. 완전탐색에서는 20 -> 17 -> 15 ->10이 중복하여 재귀호출된다.

따라서 이를 줄이기위해 2차원 배열 dp를 선언하고, 그 원소로는 "해당 칸에서 목적지까지 가기위한 경로의 개수"를 저장하였다. dfs를 탐색하기 위해 최악의 경우 3가지 방향을 탐색해야한다. (숫자가 작은 쪽으로 이동..........