[백준/Python] 14465번 : 소가 길을 건너간 이유 5

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

입력

첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.

출력

정상적으로 작동하는 연속 K개의 신호등이 존재하려면 최소 몇 개의 신호등을 수리해야 하는지 출력한다.

 

코드

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

arr = [0 for _ in range(n)]

for _ in range(b):
    arr[int(input())-1] = 1
    
left = 0
right = k-1
tmp = sum(arr[0:k])
ans = tmp

while right < n-1:
    tmp = tmp - arr[left] + arr[right+1]
    ans = min(tmp, ans)
    left += 1
    right += 1
    
print(ans)

 

풀이 과정

1. 고쳐야하는 고장난 신호등을 1로 표시

2. K 간격만큼에서 고쳐야하는 신호등 수를 그 1들의 합으로 계산 시작

3. 하나씩 옆으로 밀면서 첫번째 요소를 빼고 다음 요소를 더하며 최소값 업데이트