https://www.acmicpc.net/problem/1520
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으
www.acmicpc.net
0 <= nx && nx < m && 0 <= ny && ny < n 라고 써야 하는데 0 <= nx랑 0 <= ny를 고려하지 않아서 한참 헤맸다..
어제 푼 문제랑 비슷한 문제인 것 같은데 왜 이 문제는 골3인지 잘 모르겠다ㅋㅋ
아 근데 이제 풀이를 확실히 이해한 것 같다.
dp[y][x]는 (x, y) 부터 (n - 1, m - 1)까지의 아래 그림의 가능한 모든 파란색 경로의 개수다.
중복처리를 하지 않을 경우, 어떤 점 (x, y)를 지나갈 때 마다 (x, y) 부터 (n - 1, m - 1)까지의 경로의 개수를 매번 다시 구해야 하기 때문에 지수 시간이 걸린다.
반면 중복처리를 할 경우, 어떤 점 (x, y)를 지나가는 다른 경로를 탐색할 때 (x, y) 부터 (n - 1, m - 1)까지의 경로는 굳이 다시 구하지 않고 그냥 dp[y][x]를 반환받아 더하면 되기 때문에 시간이 훨씬 절약된다.
'코딩테스트 > 백준' 카테고리의 다른 글
| [백준] 2293번: 동전 1 (0) | 2023.10.06 |
|---|---|
| [백준] 2294번: 동전 2 (0) | 2023.10.05 |
| [백준] 1890번: 점프 (0) | 2023.10.03 |
| [백준] 11048번: 이동하기 (0) | 2023.10.02 |
| [백준] 2632번: 피자판매 (0) | 2023.09.29 |