내리막 길
-
백준 1520번 내리막 길 :: 마이구미알고리즘 풀이/동적계획법 2017. 10. 12. 09:35
이 글은 백준 알고리즘 문제 1520번 "내리막 길" 을 풀이한다.풀이 방법은 DFS + DP(동적계획법) 을 통해 해결한다.DFS - http://mygumi.tistory.com/1021520번 - https://www.acmicpc.net/problem/1520 단순히 모든 경로를 탐색한다면, 시간 초과를 경험하게 된다.시간을 줄일 수 있는 방법은 다음과 같다.20 지점에 오면 더이상 탐색할 필요가 없이 경로가 존재한다는 것을 찾을 수 있다.존재하는 경로를 활용하는 방법으로써, 동적계획법을 이용할 수 있다. dp[y][x] = (y, x) 지점일 때 존재하는 경로의 갯수 DFS를 완벽히 이해하고 있다면, 쉽게 코드를 이해할 수 있다.* dp배열을 -1로 초기화한 이유는 방문여부를 위함이다. 1234..