[백준 1520][Java] 내리막 길

https://www.acmicpc.net/problem/1520 풀이굉장히 어려웠던 문제입니다. DFS와 메모이제이션 기법을 적절히 사용해야 하는 문제였습니다. 풀이를 생각하지 못 하고 검색을 통해 해결했습니다. 첫 번째는 완전 탐색을 떠올렸습니다. DFS와 백트래킹 기법을 사용해서 완전 탐색을 하면 갈 수 있는 길의 개수를 구할 수 있습니다. 하지만 N과 M의 최대 크기는 500이었고 최대 칸의 개수는 250,000이었기 때문에 시간 초과가 발생합니다. 두 번째는 DP를 떠올렸습니다. dp[x][y]를 "좌표 (x, y)까지 도착할 수 있는 경우의 수"라고 정의하면 문제를 해결할 수 있을 것 같았습니다. 그래서 (0, 0)부터 (n-1, m-1)까지 dp 값을 구하면 해결할 수 있을 것 같았는데 문제..

2025.02.17