[백준] 2559 - 수열

1. 문제 요약

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

연속된 K일 동안의 온도 합 중에서 최댓값을 구하는 문제다.

예를 들어,

3 -2 -4 -9 0 3 7 13 8 -3

 

이 주어졌을 때,

• K = 2 → 최대 합 = 21
• K = 5 → 최대 합 = 31

---

2. 처음 접근 (시간초과 발생)

처음에는 이렇게 풀었다.

 

for i in range(n):
    for di in range(1, k):
	    pannels[i] += pannels[i+di]

3. 문제점

• 매 시작점마다 K개를 다시 더함
• 시간복잡도: O(N × K)

최악의 경우:

100,000 × 100,000 → 10^10

 

👉 시간초과 발생

---

4. 핵심 아이디어: 슬라이딩 윈도우

이 문제의 핵심은

"연속된 구간의 합을 매번 다시 구할 필요가 없다"

---

🔄 이전 합을 재활용하기

현재 구간:

a[i] + a[i+1] + ... + a[i+k-1]

 

다음 구간:

a[i+1] + a[i+2] + ... + a[i+k]

 

👉 차이점은 단 2개

• 빠지는 값: a[i]
• 추가되는 값: a[i+k]

---

✨ 따라서

 

다음 합 = 이전 합 - 빠지는 값 + 새로 들어오는 값

 

---

5. 최적 풀이 코드

 

import sys
input = sys.stdin.readline

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

current = sum(temperatures[:k])
answer = current

for i in range(k, n):
    current += temperatures[i] - temperatures[i-k]
    answer = max(answer, current)

print(answer)

---

⏱️ 시간복잡도 분석

• 초기 합 계산: O(K)
• 이후 슬라이딩: O(N-K)

👉 전체: O(N)