[백준/파이썬] 2559번: 수열

문제

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

풀이

• n일 동안의 온도
• 연속된 k일의 온도 합 중 최대값

누적합 알고리즘을 이용하면 해결할 수 있는 문제입니다.
11659번에서 사용한 알고리즘을 이용하면 됩니다.

누적합 배열 생성

num = [0] # 누적합 배열
tmp = 0
for i in arr:
    tmp += i # 누적합 계산
    num.append(tmp) # 배열에 값 추가

결과 배열에 원하는 일수의 값을 추가하여 최대값을 찾으면 해결

res = []
for i in range(n-k+1): # 연속된 k일 만큼의 값을 구하기 위해 n-k
    res.append(num[i+k]-num[i])

print(max(res))

코드

import sys
input = sys.stdin.readline

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

num = [0]
tmp = 0
for i in arr:
    tmp += i
    num.append(tmp)

res = []
for i in range(n-k+1):
    res.append(num[i+k]-num[i])

print(max(res))