[백준/Python] 2559 수열

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

 

 

사용 알고리즘: 누적 합

 

 

입력

• 온도를 측정한 전체 날짜의 수 N (2 <= N <= 100,000)
• 합을 구하기 위한 연속적인 날짜의 수 (1 <= K <= N)

 

문제에 주어진 제한 시간가 1초이기 때문에 파이썬 내장 함수인 sum 을 사용하면 시간 초과로 실패한다. 

- sum 의 시간 복잡도는 O(n)

- 전체 날짜 수 N 을 K 개의 날짜로 묶는다면 (N-K+1) 묶음이 나옴 -> 계산을 위해 for 문을 (N-K+1) 번 돌아야 함

 

최악의 경우를 생각해보면 K=1 일 때 for 문을 N 만큼 돌면서 돌때마다 sum 함수를 호출하게 되고 이때 총 시간 복잡도는 대략적으로 O(n^2) 이 된다. 그렇기 때문에 시간 초과가 뜰 수 밖에 없다. -> 누적 합 알고리즘을 사용하자

 

누적 합을 계산해서 넣을 배열 s 초기화하고, 배열에 첫번째 값을 계산해서 넣어줌

연속된 K 일의 날짜이기 때문에 처음 ~ K 번째 인덱스까지 배열 s 에 첫번째 값을 넣어줌

s = []
s.append(sum(tem[:K]))

 

 

for 문을 돌면서 계산

for i in range(N-K):
    s.append(s[i] - tem[i] + tem[K+i])

 

 

※ 그림 참고

 

 

 

전체 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
tem = list(map(int, input().split()))

s = []
s.append(sum(tem[:K]))

for i in range(N-K):
    s.append(s[i] - tem[i] + tem[K+i])

print(max(s))