15678번: 연세워터파크

15678번: 연세워터파크 - DP

kks227님 블로그의 동적계획법 4를 읽고 인상 깊어 작성하게 되었다.

이 문제는 임의의 시작점에서 번호가 증가하는 방향으로 징검다리를 건너게 되는데

한번에 D개 이하의 징검다리를 뛰어넘을 수 있을 때 점수의 최댓값을 구하는 문제이다.

풀이는 간단하다.

어떤 도착점 k의 관하여 dp(k)를 도착점 k에 도착했을 때 얻을 수 있는 최대 점수라 하면,

dp(k)는 max(0, k-D) ~ k까지의 dp값 중 최댓값이 된다.

이후 모든 i에 대하여 dp(i)의 최댓값이 답이다.

이 때 구간에 대하여 최댓값을 구하는 과정을 반복하여야 한다.

구간이기에 구간 트리를 이용하여 O(lgN)만에 최댓값을 찾을 수 있고

이는 시간복잡도가 O(NlgN)만에 문제를 해결할 수 있다.

이 때 kks227님의 블로그에서는 덱을 이용하여 이 문제를 O(N)만에 풀게 되는데

덱 안에 우리가 알고 싶은 부분의 가장 긴 감소하는 부분수열의 정보를 넣어 이 문제를 해결한다.

매 단계마다 가장 긴 감소하는 부분수열이 들어있다면

덱에 가장 앞에 있는 값이 최댓값을 가르키는 인덱스일 것이고,

인덱스가 max(0, k-D)를 넘어 갈 경우 이 원소를 빼었을 때도 덱에는 그 원소 다음으로 큰 것이

들어있기에 해결이 가능한 것이다!

아래와 같은 순서로 정리할 수 있다.

1. 덱의 앞에 들어있는 인덱스가 k-D보다 작다면 버린다.

2. dp(k) = 덱의 앞에 들어있는 값이 가르키고 있는 최대값 + k에 도착했을 때 얻을 수 있는 점수

3. 덱의 뒤에서 dp(k)보다 작은 점수가 있다면 버린다.

4. 덱의 뒤에 dp(k)와 인덱스 정보를 넣는다.

이렇게 구간의 최댓값 또는 최솟값을 구하는 방법으로 쓰일만한 테크닉인 것 같다.

덱으로 풀 수 있는 문제가 있다니..! 정말 많은 도움이 되었습니다. 감사합니다.