[백준 14465] 소가 길을 건너간 이유 5 (Silver 2)

문제

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

접근

• 누적 합, 또는 슬라이딩 윈도우로 접근 가능
• 고장난 신호등에 대해 입력할 때, 해당 배열을 1로 체크하는 것이 포인트
• 이 후에 누적 합을 계산하고 k부터 n까지 포문으로 prefix_sum[i] - prefix_sum[i-k] 값 중 가장 작은 값을 answer에 넣는다.
  

Code

import sys

n, k, b = map(int, sys.stdin.readline().split())
arr = [0] * (n+1)
answer = sys.maxsize
prefix_sum = [0] * (n+1)
for _ in range(b):
    i = int(sys.stdin.readline())
    arr[i] = 1

for i in range(1, n+1):
    prefix_sum[i] = prefix_sum[i-1] + arr[i]
    
for i in range(k, n+1):
    answer = min(answer, prefix_sum[i] - prefix_sum[i-k])
print(answer)