[백준/Python] 14465번: 소가 길을 건너간 이유 5 (슬라이딩 윈도우)

1.문제

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

14465번: 소가 길을 건너간 이유 5

2.해결방법

- 누적합으로 시도해보았으나 .. 실패하고 알고리즘 분류를 보니 슬라이딩 윈도우! 방식이 있어서 슬라이드 윈도우를 통해 구현하였다. 

- 신호등 (traffic)을 0으로 표시하고 고장난 신호등을 추후에 1로 표시해준다.

    - 슬라이딩 윈도우를 통해 k개의 신호등이 존재하도록 신호등을 수리할 때 필요한 최소한의 수리 작업을 계산한다. 

    - k사이즈안에서 고장난 신호등(0)을 찾는다. 

   - 윈도우를 이동시키며 맨 앞or 맨 뒤에 있던 신호등이 고장인지를 체크하면서 cnt값을 + - 해준다 ~~! 

 

3. 코드

n,k,b = map(int,input().split())

traffic = [0]*(n+1)
#고장난 신호등
broken =[int(input()) for _ in range(b)]

for i in broken:
    #고장난 신호등 1으로 표시하기
    traffic[i-1] = 1

min_repairs = sum(traffic[:k])

# 슬라이딩 윈도우
cnt = min_repairs

for i in range(1,n-k+1):
    if traffic[i-1] == 1:
        cnt -= 1
    if traffic[i+k-1] == 1:
        cnt += 1
    min_repairs = min(min_repairs,cnt)

print(min_repairs)