다이나믹프로그램1 [백준] 1520 내리막 길 (Java) [1520 내리막 길] 난이도: 골드4 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 문제 입력 출력 [아이디어] 처음에는 일반 DFS로 풀었다가 시간 초과가 났다. (다시 생각해보니 대략 500 * 500 * 500 * 500 * 4 정도의 시간이 걸리므로 시간 초과가 나는 것은 당연했다.) 시간 초과가 났기 때문에 DP로 풀어야 하나는 것은 알아챘지만 어떻게 DP를 적용해야 하는지 모르겠어서 구글링을 해봤다. 이 분이 설명을 위해 만들어 놓은 애니메이션으로 접근 방법을 알아 차릴 수 있었다. [백준][.. 2022. 4. 4. 이전 1 다음
