142. 2559(수열)

import sys
input = sys.stdin.readline

N,K = map(int,input().split())
num = list(map(int,input().split()))
sum = 0

numSum = [0]
numArr = []

for val in num:
    sum += val
    numSum.append(sum)
    
for i in range(K, N+1):
    numArr.append(numSum[i] - numSum[i-K])

print(max(numArr))

문제요약

측정한 온도 전체 날짜는 N이다. K는 합을 구하기 위한 연속적 날짜 수이다.

날짜 N 의 연속적인 날짜 K의 합은 얼마인가?

설명

누적합을 쓰면 매우 빠르게 문제를 풀 수 있다.

맨위는 입력받은 값이고 그 입력받은 값을 기준으로 누적합을 구하면 가운데 줄과 같다.

여기서 만약 2틀치를 받는 다고하자. 그러면,

다음 같이 누적합을 이용하여 값을 구할 수 있다.

 

이 코드를 짜면

for val in num:
    sum += val
    numSum.append(sum)

처음 값은 0으로 하고 값을 점차 추가시킨다.

 

for i in range(K, N+1):
    numArr.append(numSum[i] - numSum[i-K])

K번째 부터 시작한다.(0부터 해도 되지만 하면 식이 복잡해짐.)

인덱스가 [i] 의 누적합과 인덱스가 [i-K] 의 누적합을 빼주면 된다.

이 식은 결국  인덱스가 느린 것 - 빠른 것으로 해주는 것이다.

 

예를 들어 index 2 인 것 1 과 index 0인것 0 을 빼주면 1일차, 2일차 누적합은 1이 된다.

 

이런 식으로 끝까지 구하고 max를 통해 최대값을 구해주면 된다.