점프
-
백준 1890번 점프 :: 마이구미알고리즘 풀이/동적계획법 2017. 8. 15. 17:41
이번 글은 백준 알고리즘 문제 1890번 "점프" 를 다뤄본다.본인의 실력으로는 BFS, DFS 둘 다 시도해봤지만 도저히 맞을 수가 없었다.그리하여 동적계획법으로 문제를 접근했다. N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다.가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오. 각 칸을 기준으로 거리를 통해 갈 수 있는 지점에 경로의 개..