boj 1520

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. Logic 기본 DFS, 백트래킹 문제지만 시간복잡도때문에 메모이제이션을 활용하여 시간복잡도를 줄여줘야 한다. 즉 DFS와 DP를 합친 문제. 여기서 dp배열이 의미하는 것은 input[ny][nx]까지 갈 수 있는 경우의 수이다. 그리고 원래 DFS에서는 갔던 곳을 또 가지 않도록 무한루프에 빠지지 않도록 vis배열을 갱신해줘야 하지만 여기서는 항상 작은곳으로만 가기 때문에 vis배열을 갱신해 ..