백준 1520번 내리막 길 JAVA

요구사항 정의

 

• 크기가 N x M인 지도에 각 칸마다 높이 존재
• 시작점 (0, 0)에서 도착점 (N-1, M-1)까지 높이가 더 낮은 칸으로만 이동 가능
• 이동은 상하좌우로만 가능
• 도착점까지 갈 수 있는 총 경로의 수

 

 

풀이 방법 

2024 HSAT, 회사 코테 등 엄청 많이 나온 문제 유형이었지만 정확한 풀이 방법을 몰라 매 번 틀렸던 문제이다.

당시에는 DFS, 다익스트라로 풀었다가 시간초과 발생했었음.

 

문제의 핵심은 중복되는 경로를 DFS + DP로 Memoization하는 것

이미 한 번 계산한 경로는 다시 계산하지 않도록 dp[y][x]에 저장

 

한 지점에서의 경로 수는 다른 지점에서 재사용될 수 있다

 

 

코드

 

 

ps. https://www.acmicpc.net/problem/1937 문제도 DFS + DP로 풀 수 있는 비슷한 유형의 문제