📌문제

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.

예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,

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

모든 연속적인 이틀간의 온도의 합은 아래와 같다.

이때, 온도의 합이 가장 큰 값은 21이다.

또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,

이때, 온도의 합이 가장 큰 값은 31이다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

---

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.

---

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

---

---

📌코드

❌시간초과1

import sys
input = sys.stdin.readline

N, K = map(int, input().split())  # 전체 날짜 수, 연속적인 날짜 수
temps = list(map(int, input().split()))
sum_temp = [0]

for i in range(N - K + 1):
    cnt = 0
    for j in range(i, i + K):
        cnt += temps[j]
    sum_temp.append(cnt)

# print(sum_temp)
print(max(sum_temp))

이중 for문을 사용했을 때 시간초과가 발생했다.

❌시간초과2

import sys
input = sys.stdin.readline

N, K = map(int, input().split())  # 전체 날짜 수, 연속적인 날짜 수
temps = list(map(int, input().split()))
MAX = 0

for i in range(N - K + 1):
    sum_temp = sum(temps[i:i+K])
    MAX = max(MAX, sum_temp)

print(MAX)

리스트를 슬라이싱하여 최댓값을 구했을 때도 시간초과가 발생했다.

⭕정답

import sys
input = sys.stdin.readline

N, K = map(int, input().split())  # 전체 날짜 수, 연속적인 날짜 수
temps = list(map(int, input().split()))
sum_temp = sum(temps[:K])         # 첫 구간합
MAX = sum_temp


for i in range(N - K):            
    sum_temp += temps[i + K] - temps[i]
    if MAX < sum_temp:            # MAX = max(MAX, sum_temp) 보다 빠름
        MAX = sum_temp

print(MAX)

---

📌풀이

1. 전체 날짜 수 N = 10, 구하고자 하는 연속적인 날짜 수 K = 5라고 하면
   1일~5일, 2일~6일, 3일~7일, 4일~8일, 5일~9일, 6일~10일
   총 6개 구간합만 구하면 됨 (N - K + 1)

2. 1일~K일, 리스트로 0번째 인덱스부터 K-1번째 인덱스까지의 구간합이 첫번째 구간합이며, 처음 최댓값으로 저장

   sum_temp = sum(temps[:K])        
   MAX = sum_temp

3. 두번째 구간합은 첫번째 구간합에서 K번째 인덱스값을 더하고 0번째 인덱스값을 빼서 구할 수 있음

   sum_temp += temps[0 + K] - temps[0]

4. 현재의 최댓값보다 새로운 구간합이 더 크면 새로운 구간합을 최댓값으로 저장

   if MAX < sum_temp:
       MAX = sum_temp

5. 위 과정을 0번부터 N-K-1번까지 반복
   => N = 10, K = 5, i = 4일 때

   sum_temp += temps[9] - temps[4]

   마지막 값이 더해지기 때문에
   i = 5일 때 리스트를 벗어나게 되므로 IndexError가 발생한다.