백준 2559 수열 (실행 시간 줄이기) (파이썬)

풀이 및 해석(주석)

import sys

N, K = map(int, sys.stdin.readline().split())
tmp = list(map(int, sys.stdin.readline().split()))
lst = []
lst.append(sum(tmp[:K]))        # 미리 첫 번째 요소 부터 K번 까지의 수를 더해준 값을 lst에 넣어준다. 

result = -0xfffffff
for i in range(0, N-K):     
    lst.append(lst[i] - tmp[i] + tmp[K+i])   # 이 과정에서 sum을 이용하지 않고 lst의 i값과
                                             # tmp의 인덱스를 조절 해서 뺴주고, 더해준다.
lst.sort()

print(lst[-1])

 

---

후기

문제 자체는 쉽지만, 최적화 문제였다.

풀이의 핵심은 for문을 통해 sum을 반복하지 말 것.

따라서, 미리 첫 번째 요소 부터 K번째 요소 까지 더해준 값을 저장하고, 

for문 안에서는 인덱스를 조절해 -와 +을 이용하여 lst에 넣어 주는 것이다.

예를 들어,

n, k = 10, 5

tmp = [3 -2 -4 -9 0 3 7 13 8 -3]

이면 미리 3부터 0까지의 수를 다 더해준 값을 저장하고

for문에서 만약 -2를 가리킨 다면, 3(index = 0)을 빼주고 3(index = 5)를 더해준다.