[코딩테스트 공부] 수열

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

이 문제도 결국에는 구간합 문제입니다. 코드부터 보시죠

import sys

# 2559 수열
input = sys.stdin.readline

N, K = map(int, input().split())
temperature_list = [0] # 온도의 누적 합을 저장하는 리스트
sum = 0

for temperature in map(int, input().split()):
    sum += temperature
    temperature_list.append(sum)
    
maxv = temperature_list[K] # 처음에는 첫 날부터 K번째 날까지 합해서 일단 넣어둠
start, end = 1, N - K + 1

while start <= end:
    interval_sum = temperature_list[start + K - 1] - temperature_list[start - 1]
    
    if interval_sum > maxv:
        maxv = interval_sum
        
    start += 1
    
print(maxv)

일단은 구간합 알고리즘을 활용하기 위해서 temperature_list에는 미리 누적합을 계산해둡니다.

그리고 maxv에는 최초 슬라이딩 윈도우의 partial sum을 미리 저장해둡니다. 그리고 while문을 돌면서 maxv를 갱신합니다.

while문 내부 loop가 한 번 종료되기 직전에 start를 1 증가시키면 자연스럽게 윈도우가 슬라이딩되면서 다음의 구간합을 계산할 수 있습니다.

마지막에는 maxv를 출력해줌으로써 문제가 해결됩니다.

이 글을 참고하시면 이해가 더 잘 되실겁니다

• 수열의 합 : https://velog.io/@18k7102dy/coding-test-sixth-1