[백준] 2559번 수열

💡문제접근

• 이전 포스팅에 있었던 [[백준] 11659번 구간 합 구하기 4]와 동일한 유형의 누적 합 문제였다. 누적 합은 sum과 슬라이싱을 이용한 방법보다 시간적인 측면에서 효율성이 우수하기 때문에 알아둬야 하는 좋은 PS방법이다.

💡코드(메모리 : 39464KB, 시간 : 92ms)

N, K = map(int, input().split())
li = list(map(int, input().split()))

prefix_temperature_sum = [0]
val = 0
for i in range(len(li)):
    val += li[i]
    prefix_temperature_sum.append(val)

max = -10000001
L = 0
R = 0
for i in range(1, N-K+2):
    L = i
    R = L+K-1
    if max < prefix_temperature_sum[R] - prefix_temperature_sum[L-1]:
        max = prefix_temperature_sum[R] - prefix_temperature_sum[L-1]
print(max)

💡테스트케이스 설명

입력

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

출력

21

• 온도의 누적 합을 구해보면 다음과 같다.
  [0, 3, 1, -3, -12, -12, -9, -2, 11, 19, 16]

• 문제에서 요구한 조건대로 2일 연속 온도의 최대값을 구하는 과정을 일부만 보여주면 아래와 같다.
  1 ~ 2일 온도의 합 : 1 - 0 = 1
  2 ~ 3일 온도의 합 : (-3) - 3 = -6

이 때, 2 ~ 3일 온도의 합은 3일까지의 온도 누적 합에서 1일까지의 온도 누적합을 빼준 값이다. 이와 같은 개념을 이용해 접근해서 해결할 수 있었다.

💡소요시간 : 27m