[문제풀이 py] B2559 수열

수열 / 슬라이딩 윈도우 🚠

---

  🎠. '슬라이딩 윈도우'알고리즘을 구현할 줄 알아야한다 => '이전의 계산한 결과'를 최대한 이용하는 방식으로

[시간초과 난 코드.py]

  N, K = map(int, input().split())
  tempers = list(map(int, input().split()))
  # print(tempers)

  sum_prev = sum(tempers[:K])
  for i in range(1, len(tempers)-K):
      cur = sum(tempers[i:K+i])
      sum_prev = max(sum_prev, cur)
  print(sum_prev)                                                            

🤡. 실수한 부분
: 이전에 계산한 결과를 써먹지 못했다.

[성공한 코드.py]

  N, K = map(int, input().split())
  tempers = list(map(int, input().split()))
  # print(tempers)

  sum = sum(tempers[:K])
  prev = sum
  for i in range(K,N):
     sum -= tempers[i-K]
     sum += tempers[i]
     prev = max(sum, prev)
  print(prev)

💡. 문제 접근 방법
: 연속된 날짜의 온도의 합을 구할 때, 어차피 연속된 날짜의 길이는 K로 고정되어 있다
이를 한칸씩 오른쪽으로 이동하면서, 전의 결과와 비교하는 것에서 '슬라이딩 윈도우' 알고리즘이 생각났다.
최대한 이전에 계산한 결과를 이용하기 위해서, 한칸 이동할 때마다 이전 결과에
앞의 한개를 빼고 뒤에 한개를 더하면 시간초과 나지 않고 문제를 해결할 수 있다.