백준 2559 수열 파이썬 문제풀이 (python 누적합)

문제 보러가기

 

백준 수열 파이썬 문제풀이

3 -2 -4 -9 0 3 7 13 8 -3

이런 수의 나열이 있다.

2개씩 짝지어서 합을 구하면

이렇게 나오고, 가장 큰 값은 21이다.

 

5개씩 하면

이런 식이다.

 

여러 수열에서 몇 개씩 짝지어서 합을 구할 때 가장 크게 나오는 수가 몇인지 구하는 문제이다.

 

이 문제는 누적합으로 풀 수 있는데,

예를 들어 누적합 3번째 값에서 누적합 1번째 값을 빼면,

수열 3번째와 2번째 값의 합을 구할 수 있다는 규칙이 생긴다.

 

이를 이용해서 구현한다.

N,K = map(int, input().split())
numList = list(map(int, input().split()))
prefix = [0 for _ in range(N+1)] # 크기 1 더 긴 배열

for i in range(N):
    prefix[i+1] = prefix[i] + numList[i] # 누적합 구하기

answer = []
for i in range(K,N+1):
    answer.append(prefix[i]-prefix[i-K])
print(max(answer))

prefix라는 누적합 배열을 만든다. 

이때 현재까지 수열의 합을 다음 인덱스에 넣기 때문에 prefix의 길이는 1더 크다.

 

구한 prefix를, 연속으로 더하는 개수인 K개 전 인덱스의 prefix로 빼면 

인덱스 i까지 K개 수열의 합을 구할 수 있다.

하나하나씩 구하고 최댓값을 얻자.