[Algorithm] 징검다리 건너기

Algorithm Description::

숫자가 쓰여진 징검다리를 건너는 경우 밟은 징검다리의 숫자 만큼의 돈을 지불하는 경우 최소의 돈으로 건너는 방법을 구하는 문제이다. (단 ,2 칸 까지 점프 할 수 있다고 하자.)

1. 징검다리가 2 개 있다면 징검다리를 하나도 사용하지 않고 건널수 있으므로 지불할 돈이 없고

2. 징검다리의수가 3 개이고 쓰여진 숫자가

1 9 3

    이면, 첫 번째 징검다리를 밟고 지나간다면 1 원으로 건너는게 최소이다.

3. 징검다리 수가 10 개 이고 쓰여진 숫자가 아래와 같다면

최소로 건널수 있는 비용은 2+2+1+2 = 7 이다.

입력 방법

입력의 첫째 줄에는 징검다리 수(10000 이하인 양의 정수)가 주어지고 , 다음 줄에는 차례대로 징검다리에 씌여진 숫자(100 이하인 양의 정수)가 입력된다.

출력 방법

건널수 있는 최소 금액을 출력한다.

입출력 예

입력

10

3 2 8 2 4 9 1 2 3 4

 

출력

7

Program Description::

이번 문제를 푸는 방법에는 재귀함수를 이용해서 푸는 방법과 동적프로그래밍을 이용하여 푸는 방법 두가지가 존재한다.

하지만 재귀함수는 n이 커짐에 따라 소요되는 시간이 기하급수적으로 늘어나 실질적으로 알고리즘을 풀이하는데에는 한계가 있다.

그래서 동적프로그래밍(Dynamic Programming)이라는 알고리즘 기법을 사용해 문제를 풀어보았다.

Dynamic Programming Reference

:http://ruins880.tistory.com/13

:http://blog.daum.net/pooppoop365/2

이 문제에서 최적해는 징검다리를 최소비용으로 건너는 값이다.

arr : 각 징검다리의 비용이 저장 되어있는 배열.

cost : 각 징검 다리까지 가기 위한 최소비용.

l : 각 징검다리로 가기위한 경우의 수 중 가장 적은 비용을 지불하는 징검다리.

    ( n = 4이면, n=3,n=2,n=1이 4번 징검다리로 갈수 있는 후보이다. 이 후보들중 cost가 가장 적은 징검다리 번호가 l배열에    저장된다.. ㅣ[4]는 2가 된다.)

ㅣ배열에 대해

좀더 자세히 설명하자면 10번 징검다리를 가기 위한 최소비용은 7번 징검다리를 밟는 것이고,

7번 징검다리를 가기 위한 최소비용은 4번, 4번을 가기위한 최소비용은 2번 징검다리가 될 것이다.

n=1,2,3이 x(안쓰는 )이유는 단순하다. l[1],l[2],l[3]을 가기위한 전 징검다리가 존재하지 않기때문(한번에 이동가능)이다.

이 문제의 해를 f라고 할경우 해에 도달 할수 있는 징검다리는 n,n-1,n-2가 될수 있을 것이고, 이것들의 최소비용이 징검다리를 건너는 

최소 비용이 될것이다. 

f = min(cost[n],cost[n-1],cost[n-2]);

동적프로그래밍과 재귀함수의 큰 차이점은 위 링크에 걸려있듯이, 값을 미리 저장하여 따로 계산할 것없이 테이블에서 빼서쓰냐,

다시 계산해서 쓰냐의 차이이다. (피보나치수열을 떠올려보자)

Program Code::