[백준 14465] 소가 길을 건너간 이유5

문제

농부 존의 농장에 원형 길이 있다고 했지만, 길은 그뿐만이 아니다. 그 옆에 일자형 길이 있는데, 1번부터 N번까지의 번호가 붙은 횡단보도 N (1 ≤ N ≤ 100,000)개로 이루어져 있다. 교통사고를 방지하기 위해 존은 각 횡단보도에 신호등을 설치해 놓았다. 그러던 어느 날, 강력한 뇌우로 인해 몇몇 신호등이 망가졌다. 존은 연속한 K개의 신호등이 존재하도록 신호등을 수리하고 싶다. 이번에도 우리가 존을 도와주자.

 

입력

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

 

출력

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

---

접근

0으로 초기화된 리스트에서 고장난 신호등 번호에 대한 인덱스는 1로 표시한다. 이어서 누적합을 계산한다.

이렇게 되면 특정 연속된 구간에서 수리해야할 신호등 개수를 알 수 있게 된다. 이를 활용하여 K개의 연속된 수에서 수리해야하는 신호등의 최소개수를 구한다.

 

구현

- 0으로 초기화된 리스트인 broken_list를 생성한다.

- 고장 신호등에 대한 번호를 입력받아 해당 번호의 인덱스를 1로 표시한다.

- 이어서 1번 신호등부터 N번 신호등까지 고장난 신호등 개수의 누적합을 구한다.

N, K, B = map(int, input().split())
broken_list = [0 for _ in range(N+1)]

for _ in range(B):
    b = int(input())
    broken_list[b] = 1

for i in range(1, N+1):
    broken_list[i] += broken_list[i-1]

- 최솟값을 구하기위해 answer를 B로 초기화한다. 수리해야 할 신호등은 B를 초과할 수 없다.

- 이제 K부터 탐색을 하여 

- 현재 인덱스에서 K 이전의 고장난 신호등 개수를 빼준다.

- 그렇다면 해당 K개의 연속된 구간에서 수리해야 할 신호등의 개수가 될 것이고

- 이를 최솟값 비교를 한다.

answer = B
for i in range(K, N+1):
    answer = min(answer, broken_list[i] - broken_list[i-K])

---

전체 코드

import sys
input = sys.stdin.readline

N, K, B = map(int, input().split())
broken_list = [0 for _ in range(N+1)]

for _ in range(B):
    b = int(input())
    broken_list[b] = 1

for i in range(1, N+1):
    broken_list[i] += broken_list[i-1]

answer = B
for i in range(K, N+1):
    answer = min(answer, broken_list[i] - broken_list[i-K])

print(answer)