[알고리즘 문제] 징검다리

티바이트 2016. 10. 27. 00:42

2016. 10. 27. 00:42

출처

Koreatech OnlineJudge(링크)

문제이해

배열의 처음부터 끝까지 주어진 간격(1~3) 이하만큼 숫자를 고를 때

최소비용을 구하는 동적 프로그래밍 문제이다.

문제에 직접적으로 서술되어 있지는 않지만, 설명을 보면 첫 번째나 마지막 징검다리는 밟지 않아도 된다는 것을 알 수 있다.

문제접근

간단한 유형의 DP(Dynamic Programming)문제이다.

예를 들어 {28, 85, 89, 70, 1, 43}이 주어질 때는,

89, 1을 고르면 되는데, 89까지의 최적해가 전체 문제의 부분해가 될 수 있는 재귀적 속성(recursive property)이 있다.

배열의 왼쪽부터 시작해서 요소 하나씩 검사해 나가면 되는데,

먼저 처음 원소인 28에 다다르기 위한 최소비용은 당연히 28이다.

그 다음 원소인 85에 가는 방법은 28을 거쳐서 가는 방법과, 85로 바로 가는 방법이 있는데,

85로 바로 가는 방법이 최소비용이므로 최소비용은 85이다.

그 다음 원소인 89 역시 (89까지 도착하기 위한)최소비용이 89이다.

그 다음 원소인 70부터는 아래와 같이 3가지 방법이 있다.

1) 28 -> 70

2) 85 -> 70

3) 89 -> 70

이 중 최소비용은 1번으로, 70까지의 최소비용은 28+70=98이 된다.

그 다음 원소인 1까지 가는 최소비용은 같은 원리로 3가지가 있다.

1) 85까지의 최소비용 + 1

2) 89까지의 최소비용 + 1

3) 70까지의 최소비용 + 1

기억해 놓은 정보로 계산하면,

1) 86

2) 90

3) 98

이므로 1까지의 최소비용은 86이 된다.

이러한 과정을 배열의 끝까지 반복하면 된다.

문제에서 주어진 점프력이 3이므로 현재 위치에서 3개 전까지의 수를 봐야 하는 것이다.

실행결과

티바이트