[BOJ/python]2208번 보석줍기

백준 2208번 보석줍기 파이썬

출처 - https://www.acmicpc.net/problem/2208

2208번: 보석 줍기

까다로운 DP를 풀어보고 싶어서 검색해서 풀었는데 생각보다 쉽게 풀렸다. 투 포인터 생각도 났는데 최댓값을 구해야 되는 문제이기 때문에 일단 구간합부터 구하고 시작했다.

1. 풀이

보석은 반드시 M개 이상 연속해서 주워야 한다. 즉 길이가 M이상인 구간합 중 최대를 찾으면 된다.

• dp[i][0]에는 현재 보석을 선택하지 않았을 때 최대 구간합을 저장한다. 즉 현재 이전에서 이미 M개 이상의 연속한 보석을 주운 경우이다.
• 이 경우는 직전 인덱스에서도 보석을 줍지 않은 경우와 직전 인덱스까지 연속하여 보석을 주운 경우 두 가지 뿐이다.
• dp[i-1][0]과 dp[i-1][1] 중 큰 값을 저장하게 된다.
• dp[i][1]에는 현재 보석을 선택했을 때 최대 구간합을 저장한다. 즉 이전 인덱스까지 보석을 연속해서 주운 경우이다.
• 현재 인덱스를 포함하여 정확하게 M개를 주운 경우와 이미 M개 이상을 주웠고 현재 인덱스까지 주운 경우 두 가지 경우다 있다.
• dp[i-1][1] + A[i] 와 A[i-M] +... + A[i] 중 큰 값을 저장한다. 이 때 후자의 경우 prefix를 이용하여 간단하게 구할 수 있다.

2. 코드

#보석 줍기dp
N,M = map(int, input().split())
A = [ int(input()) for _ in range(N)]
prefix = [0 for _ in range(N)]
prefix[0]=A[0]
for i in range(1, N):
    prefix[i] = prefix[i-1]+A[i] #benefit[k] = prefix[k]-prefix[k-M]  : k번째 인덱스를 마지막으로 M개 구간합

dp= [[0,0] for _ in range(N)]  #현재 선택X / 선택 
dp[M-1][1] = prefix[M-1]

for i in range(M,N):
    
    tmp1= dp[i-1][0] #이전에서도 보석 안주웠을 때
    tmp2= dp[i-1][1] #이전 보석 주웠을 때
    
    tmp3 = tmp2 + A[i] #이전 보석 주운거에 현재거 까지
    tmp4 = prefix[i] - prefix[i-M] #현재 기준으로 딱 M 개 주웠을 때
    
    dp[i][0] = max(tmp1, tmp2)
    dp[i][1] = max(tmp3, tmp4)

print(max(dp[N-1]))