[백준 2559번] 수열

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

import sys

input = sys.stdin.readline

n, k = map(int,input().split())

temp_list = list(map(int,input().split()))

value = sum(temp_list[:k])

answer = value

for i in range(k,n):
    
    value -= temp_list[i-k]
    value += temp_list[i]

    answer = max(answer,value)

print(answer)

이번 문제는 N일 동안 측정된 온도에서 연속 K일간 측정했을 때의 최댓값을 구하는 문제이다.

해당 문제는 단순히 완전탐색으로 풀게되면 O(N*K)의 시간복잡도가 나오게 되는데, N이 최대 10^5 이므로 시간초과가 발생하게 된다.

따라서 슬라이딩 윈도우를 활용하여 첫 K 길이의 온도의 합부터 마지막 온도까지 값을 구하면서 answer를 업데이트 해주었다.(시간복잡도 O(N))