누적합 | 백준 2559 수열

 

문제

 

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

N일 간의 온도가 주어졌을 때 연속적인 K일 간의 온도의 합이 가장 큰 값을 찾아라.

 

입력

 

• 첫째 줄: N과 K가 공백을 사이에 두고 주어짐 (2<=N<=100,000)
• 둘째 줄: 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어짐 (-100<=온도<=100)

 

출력

• 연속적인 K일의 온도의 합이 최대가 되는 값

 

작성한 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
temps = list(map(int, input().split()))
prefix = [0] * (N+1)
prefix[1] = temps[0] 

#첫날부터 마지막날까지의 누적합 미리 계산
for i in range(1, N):
    prefix[i+1] = temps[i] + prefix[i]

K_sums = [0] * (N-K+1)

#계산해 둔 prefix로 연속적인 K날 동안의 합 계산
for j in range(0, N-K+1):
    K_sums[j] = prefix[K+j] - prefix[j]

print(max(K_sums))

 

 

누적합

 

누적합 문제는 말 그대로 누적된 합을 미리 계산해두는 것에서 시작한다.

 

예를 들어 2번째 원소부터 4번째 원소까지의 합을 물었을 때 누적합 계산값이 없다면

nums[1] + nums[2] + nums[3] 와 같은 식으로 원소 하나 하나를 더해야하지만

누적합을 계산해 둔 경우 prefix[3] - prefix[0]과 같이 O(1) 시간에 답을 구할 수 있다.

 

• prefix[0] = 0 으로 두면 인덱스 관리가 쉬워진다.
• prefix[i] = i번째까지의 누적합
• 구간 [a, b]의 합은 prefix[b] - prefix[a-1]으로 계산