[백준 15678번] 연세워터파크 (Python3)

import sys,heapq
input = sys.stdin.readline

N,D = map(int,input().split())

step = [*map(int,input().split())]

DP = [0]*N

hq = []
for i in range(N-1,-1,-1):
  DP[i] += step[i]
  while hq and hq[0][1] > i+D:
    heapq.heappop(hq)
  if hq:
    DP[i] -= hq[0][0]
  if DP[i] > 0:
    heapq.heappush(hq,(-DP[i],i))

print(max(DP))

최솟값 찾기 11003번: 최솟값 찾기 (acmicpc.net) 문제와 거의 똑같은 방식으로 해결하였다.

일단 이 문제에서 징검다리를 한쪽 방향으로만 건너야 한다는 말은 없지만, 한쪽 방향으로만 걸어도 상관없다. 어차피 1 2 3 이 있을때 1 3 2 순으로 지나가든, 1 2 3 순으로 지나가든 점수는 똑같기 때문이다. 따라서 나는 무조건 오른쪽으로만 점프한다고 가정하고 문제를 풀었다.

 

이를 토대로 설명하면,

1. 마지막 징검다리부터 시작해서 현재의 위치에서 오른쪽으로 이동할 때 얻을 수 있는 최대값을 DP값으로 잡는다.

2. 현재의 DP값이 0보다 큰 경우, 최대힙에 DP값과 인덱스를 튜플로 넣는다. (0보다 작은 경우는 필요하지 않다. 원하는 지점에 들어와서 원하는 지점에 나가는것이 가능하기 때문)

3. 최대힙에서 점프할 수 있는 거리 밖의 값은 pop하고 나머지 중 가장 큰 값을 DP에 더해준다.

4. 최댓값을 출력한다.

 

즉, 최솟값 찾기 문제의 알고리즘으로 최댓값을(최소힙을 최대힙으로 바꿔주기만 하면 된다) 찾은 다음, 해당 최댓값을 DP에 더해주면서 푸는 것이다.

 

 

오늘의 교훈) 여러가지 알고리즘을 적재적소에 활용하자