백준 2208 : 보석 줍기 (Python)

본문 링크

import sys
input=sys.stdin.readline

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

L=[]
for i in range(N):
    L.append(int(input()))


Prefix_sum=[0]*(N+1)

for i in range(1,N+1):
    Prefix_sum[i]=Prefix_sum[i-1]+L[i-1]


dp=[0]*(N+1)

check=2000
for i in range(1,N+1):
    if i>=M:
        check=min(check,Prefix_sum[i-M])
        dp[i]=max(dp[i-1] , Prefix_sum[i]-check)
    else:
        dp[i]=dp[i-1]

print(dp[-1])

📌 어떻게 접근할 것인가?

이문제는 3가지 규칙이 존재한다.

• 보석을 줍다가 뒤로 돌아갈수 없다. 즉 연속적으로 보석을 주워야한다.
• 보석을 줍다가 멈추면 함정이 발생한다. 다만 보석을 $M$ 개 이상 주우면 함정이 발생하지 않는다.
• 보석을 가치를 최대로 되게끔 주운다.

문제에서는 보석의 개수와 $M$ 의 값 , 그리고 보석하나하나의 가치가 주어진다.
우리는 보석을 주워 가치의 최대값을 주운다.

다만 이 문제에서는 가치가 음수인 보석이 존재한다.
또한 $N(1 ≤ N ≤ 100,000)$ 이기 때문에 완전탐색이 불가능하다.

그래서 $O(N)$으로 해결가능한 누적합 알고리즘과 다이나믹 프로그래밍을 사용할려고한다.

먼저 누적합 알고리즘을 사용해야겠다고 생각한 이유는 보석을 연속적으로 주워야 하기 때문이다.
따라서 누적합 배열을 만들면 특정 구간의 합을 $O(2)$에 구할수 있다.

$ex)$ $Prefix[i] - Prefix[i-M]$ -> $i-M$ 부터 $i$ 번째까지의 합

두번째로 $DP$ 배열을 사용해야한다고 생각한 이유는 구하고자 하는 값이 가치의 최대값이기 때문이다. $O(N)$ 으로 보석의 가치 최대값을 매번 확인할려면 이전값을 확인해서 보석을 들고갈지 , 들고가지 않을지 확인해주면서 이전값을 활용해야하기 때문에 $DP$ 를 쓰기로 했다.

📌 누적합과 다이나믹 프로그래밍을 어떻게 쓸것인가?

우리는 총 $M$ 개 이상의 보석만 주우면 된다. 또한 $M+1$ 개 , $M+2$ 개 또한 보석을 챙겨갈수 있다.

따라서 원래 식은 $dp[i]=max(dp[i-1] , Prefix[i]-min(Prefix[0:i-M])$ 이다.
하지만 매번 $min(Prefix[0:i-M])$ 을 해버리면 시간 초과가 나므로

누적합 배열의 $0$ 부터 $i-M$ 까지의 최소값을 매번 저장해줄 check 변수 하나를 만들어서
최소값을 매번 저장해준다.

즉 반복문을 한번 돌면서 $i>=M$ 일때

• $dp[i]=max(dp[i-1] , Prefix[i]-check)$

위 점화식이 성립된다.

$Prefix[i]-check$ 가 가지는 의미는 현재까지의 누적합 배열에서 인덱스값 $M$ 이전의 배열중 최소값을 선택한다. 따라서 최대값 - 최소값은 결국 최대값으로 귀결된다.
왜냐하면 우리는 $M$ 개의 연속된 보석만 챙기면 되기 때문에
현재 인덱스가 $i$ 라면 0,1,2,3,4 ⋯ , i-M 배열중 어느 위치의 인덱스값을 선택해도 $M$ 이상의 보석을 연속적으로 챙기게 되기 때문이다. 따라서 $check$ 배열은 0,1,2,3,4 ⋯ , i-M 값중 최소값을 저장하게 된다.

$M$ 이 3일때 현재지점에서 (-3)보다 작은 모든 지점들은 $M$ 개이상 보석을 연속적을 선택하는것이 성립된다.
만약 두번째 인덱스를 선택했다면 $Prefix[7]-Prefix[1]$ , 즉 1번째부터 7번째까지 보석을 모두 주운경우이고
$0$부터 $i-M$ 까지 최소값을 선택하면 $Prefix[i]-Prefix[i-M]$ 은 자동으로 최대값이 된다.