[백준] 2559번 수열 파이썬 코드

코드

# n은 최대 100000, k는 n보다 작거나 같은 수
# 최악의 경우 10^10, O(nlogn) 이하로 해결해야함

n,k = map(int, input().split())
numlst = [*map(int, input().split())]
res = -987654321 # -100이 100000개일 경우 대비해서 작은 수 할당

arr_sum = [0]*(n+1) # 구간합을 구해 줄 리스트

for i in range(1,n+1):
  arr_sum[i] = arr_sum[i-1] + numlst[i-1]

for i in range(1,n+1):
  if i+k > n+1: break # 범위를 벗어나면 탈출
  # ex)10일까지의 온도합에서 5일차까지의 온도합을 빼면 6~10의 온도 합이 나온다
  temp = arr_sum[i+k-1]-arr_sum[i-1] 
  res = max(res, temp) # 큰 수 찾기

print(res)

처음에 연속하는 구간이 아니라 k만큼 떨어진 거리만큼의 합을 구하는 문제인 줄 알았다가 잘못 접근했음을 깨달았다. 연속하는 수만큼의 합을 구하려면 구하고자 하는 최대 범위 수까지의 구간합에서 작은 숫자까지의 구간합을 빼주면 값을 구할 수 있다. 주석에 달아둔 것처럼 6~10일까지의 온도합을 구하고 싶다면 10일차까지의 합에서 5일차까지의 합을 빼주면 되는 것을 예로 들 수 있다.