[python] 백준 2559번 - 수열

2559번: 수열 (acmicpc.net)

2559번: 수열

 

누적 합 문제이다.

처음에 for문을 두번 돌려서 답은 나왔는데 계속 시간제한이 걸렸다.

첫 인덱스부터 더해가며 누적 합을 구하는 것도 아니었기 때문에

어떻게 누적합 리스트를 만들 수 있을까 고민하였지만..

결국 다른 해설을 보고 이해했다.

 

다시 해결한 방법은 다음과 같다.

 

import sys
input = sys.stdin.readline

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

lst=[*map(int, input().split())]
psum = sum(lst[:k])
suml=[psum]


for i in range(0,len(lst)-k):
    psum = psum - lst[i] + lst[i+k]
    suml.append(psum)
    
print(max(suml))

연속합을 저장하는 리스트 psum에 처음 연속합만 sum을 이용하여 저장한다.

그리고 그 다음부터 for문을 돌면서 

두 번째 인덱스부터의 부분합은 첫 번째 부분합에서 뒤의 인덱스 값을 빼고 k번째 뒤의(즉, 바로 뒤) 인덱스 값을 더해주면 되기 때문에

위와 같이 코드를 작성하였다.