사용자 도구

사이트 도구


ps:problems:boj:15678

연세워터파크

ps
링크https://www.acmicpc.net/problem/15678
출처BOJ
문제 번호15678
문제명연세워터파크
레벨플래티넘 5
분류

DP, monotone queue

시간복잡도O(n)
인풋사이즈n<=10^5
사용한 언어Python
제출기록42440KB / 176ms
최고기록176ms
해결날짜2022/07/02

풀이

  • 문제 조건은 왼쪽과 오른쪽으로 점프가 가능하지만, 한쪽 방향으로만 점프해서 이동해도 최적값을 찾을수 있다는 것은 쉽게 떠올릴수 있다.
  • 그러면 왼쪽에서 오른쪽으로만 이동한다고 가정하고 최대값을 dp로 계산하자.
  • dp[i]를 i번째 징검다리에 도착했을때 가질수 있는 최대 점수라고 하면, dp[i] = K[i] + max(0, dp[i-1], dp[i-2], .. ,dp[i-D+1]) 로 점화식이 나온다.
  • 이 점화식을 그냥 풀면 O(nd)이지만, monotone deque 테크닉을 활용해서 O(n)에 풀수 있다.

코드

"""Solution code for "BOJ 15678. 연세워터파크".

- Problem link: https://www.acmicpc.net/problem/15678
- Solution link: http://www.teferi.net/ps/problems/boj/15678

Tags: [DP] [Monotone queue]
"""

import collections

INF = float('inf')


def main():
    N, D = [int(x) for x in input().split()]
    K = [int(x) for x in input().split()]

    deq = collections.deque([-INF])
    dp = [-INF] * D
    for dp_left, k_i in zip(dp, K):
        dp_cur = k_i + max(0, deq[0])
        while deq and deq[-1] < dp_cur:
            deq.pop()
        deq.append(dp_cur)
        dp.append(dp_cur)
        if deq[0] == dp_left:
            deq.popleft()

    print(max(dp))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Z L᠎ N U​ D
 
ps/problems/boj/15678.txt · 마지막으로 수정됨: 2022/07/02 15:13 저자 teferi