[Python]알고리즘/백준
[다이나믹 프로그래밍] ★ 1520번 - 내리막 길
[백준] 1520번 - 내리막 길 (한줄평) 오랜만에 dp 문제플 풀었더니 약간 헤맸던 문제다. dp와 dfs를 한 번에 쓰는 문제는 처음이라 낯설었던 것 같기도 하다. 꼭 복습이 필요한 문제! 풀이 시간: 60분 이내 1) 문제 해결 아이디어 n * m의 지도의 높이 정보가 주어지고 지금보다 높이가 더 낮은 곳으로만 이동하여 (0, 0)에서 (n-1, m-1)까지 이동 가능한 경로의 수를 구하는 문제다. 이 문제는 DFS + DP 를 이용하여 풀 수 있는 문제다. 오로지 DFS로만 풀려고 한다면 가능한 모든 경로의 수를 다 세야하기 때문에 아마 시간초과가 날 것이다. n, m의 범위가 1이상 500이하이기 때문이다. DFS와 DP를 이용하여 풀어야한다는 것은 알았는데 점화식을 잘못세워서 헤맸다. 처음에..
