2208. 보석 줍기 (Python)

2208번: 보석 줍기

 

풀이

1. 각 보석 가치의 누적합을 구한다.
2. for문을 통해서 M번부터 시작하여 현재 인덱스의 보석까지 주웠다고 가정했을 때 얻을 수 있는 가치의 총 합을 구한다. 

 

 보석을 주울 때 최소 M개의 보석을 연속으로 주워야 한다. 문제에서 주어진 예제처럼 M이 4라면 일단 4번째 보석부터 탐색을 시작해야 최소 M개의 보석을 줍는다고 가정할 수 있다. 

 5번 보석을 마지막으로 주웠다고 가정하면 보석은 1번 또는 2번부터 주워야한다. 5번 보석을 마지막으로 주웠을 때 보석 가치의 총 합중 최댓값은 1번 부터 주웠을 때의 경우(누적합[5] - 누적합[0])와 2번 부터 주웠을 때의 경우(누적합[5] - 누적합[1])중 최댓값이 된다. 

 위와 같은 방법으로 i번째 보석을 마지막으로 주웠을 때의 보석 가치 총 합의 최댓값을 구하면 답을 얻을 수 있다.

 

코드

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    N, M = map(int, input().split())
    costs = [0] # costs[i]: i번째 보석의 가치
    costSum = [0] # costSum[i]: i번째 보석까지의 가치 누적합

    tmpSum, res = 0, 0
    for _ in range(N):
        cost = int(input())
        costs.append(cost)
        tmpSum += cost
        costSum.append(tmpSum)

    minBase = 0 # 최소 누적합
    for i in range(M, N + 1): # M개 이상 보석을 주워야 하므로 인덱스 M부터 시작
        minBase = min(minBase, costSum[i - M]) # 0 ~ i-M까지의 누적합 중 최솟값 
        res = max(res, costSum[i] - minBase) # i번째 보석까지의 누적합 - minBase를 통해서 최댓값을 구한다.

    print(res)