[Python] 백준 2559번 : 수열

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

2559번: 수열

---

 문제 풀이

구간 합 문제이다!

n부터 m만큼의 범위의 합 자체를 계산하는 것은 쉽다. 하지만 시간이 부족하다.

 

두 가지만 생각하면 된다.

  1. sum()을 남발하면 느리다.

  2. sum(arr[n:n+m])과 sum(arr[n+1:n+m+1])의 차이는 n번째 값과 n+m+1번째 값의 차이다.

 느낀 점

그렇게 어렵지 않았지만 마지막 아이디어를 생각해내는데 시간이 조금 걸렸다! 풀어본 문제가 별로 안돼서 그런 것 같다.

 코드

from sys import stdin

n, k = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))
prefix_sum = [sum(arr[:k])]

for i in range(n-k):
    prefix_sum.append(prefix_sum[i] + arr[i+k] - arr[i])
    
print(max(prefix_sum))