[백준] 12847번 꿀 아르바이트

💡문제접근

• 처음엔 구간별 합계를 이용해서 코드를 작성했으나 시간초과가 발생했다.
• 1일부터 M일간 일을 해서 버는 최대 이익을 출력하면 된다. M = 3이면 1~3일간의 일급의 합, 2~4일간의 일급의 합... 이런 식으로 나가는 것이다. 따라서 처음에 1~M일간의 일급을 미리 구한 다음 start, end 투 포인터를 하나씩 뒤로 옮겨 가장 최대가 되는 구간을 찾으면 된다.

💡코드(메모리 : 42172KB, 시간 : 92ms)

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
price = list(map(int, input().strip().split()))

prefix_sum = 0
for i in range(M):
    prefix_sum += price[i]

start = 0
end = M
Max = prefix_sum
while end < N:
    prefix_sum = prefix_sum + price[end] - price[start]
    if Max < prefix_sum:
        Max = prefix_sum
    start += 1
    end += 1
print(Max)

💡소요시간 : 17m