Baekjoon 1520 내리막 길 JAVA

https://www.acmicpc.net/problem/1520

 

1520번: 내리막 길

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201520

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 map가 주어졌을 때 0,0에서 N-1, M-1까지 갈 수 있는

경우의 수를 구하는 문제다.

​

단 이동은 현재 자신보다 작은 값으로 민 이동이 가능하다.

​

처음에 dfs로 문제를 해결했더니 시간 초과가 발생했고,

dfs + dp로 문제를 해결했다.

​

dp 배열을 처음에 -1로 초기화해 주고 이후 dp 배열이 -1이 아니면 리턴해주고

-1이면 이제 0으로 초기화한 뒤 dfs를 진행해 주고 현재 dp 위치에 이동하는 값들을

추가해 주면 된다.

이후 최종적으로 dp 배열을 리턴해주면 되고, 만약 마지막에 도달하면 1을 리턴해주면 된다.