백준_2208_보석 줍기

문제

https://www.acmicpc.net/problem/2208

2208번: 보석 줍기

풀이

1) 연속 누적합 dp

우선, 보석의 개수를 신경쓰지 않고, 연속해서 얻을 수 있는 보석의 누적 가치합을 구한다.

이를 위해 세가지 경우를 고려한다.

• 이전 보석과 연속해서 줍는다.
• 이전 보석을 버리고, 현재 보석만을 줍는다.
• 아무 보석도 줍지 않는다.

2) M개 이상의 보석을 줍는다. prefix_sum

2-1. 현재 위치를 포함해서, 왼쪽으로 이동하면서 M개의 보석을 줍는다.

2-2. M개보다 더 선택할 수 있으므로, 왼쪽에서 연속해서 보석을 더 선택할 수 있는지 확인한다.

 

주의할점은 "아무것도 줍지 않아도 된다"는 것이다.

코드

N, M = map(int, input().split())
arr = [int(input()) for i in range(N)]

# 연속 누적합
dp = [0 for i in range(N)]
for i in range(len(arr)) : 
    # 이전 보석과 연속해서 줍거나, 현재 보석만 줍거나, 아무것도 줍지 않는다.
    dp[i] = max(arr[i]+dp[i-1], arr[i], 0)

# 최소 M개의 보석을 주워야 한다.
prefix_sum = [0 for i in range(N)]
for i in range(M, N) :
    # 현재 위치의 보석을 포함한 M개의 보석
    prefix_sum[i] = sum(arr[i-M+1:i+1])
    # 앞의 보석들을 더 선택할 수 있다.
    prefix_sum[i] += dp[i-M]

prefix_sum.append(0) # 아무것도 줍지 않아도 된다.
print(max(prefix_sum)) # 최댓값 구하기