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

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

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

유형

누적합

문제

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

입력

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

출력

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

소스코드

n, k, b = map(int,input().split())
min_fix = float('inf')

road = [True]*(n+1)

for _ in range(b):
    road[int(input())] = False

s = 1
e = 1 
fix = 0

while e < k:
    e += 1
    if road[e] == False:
        fix += 1

while e < n: 
    min_fix = min(min_fix, fix)
    e += 1 
    s += 1
    if road[e] == False: 
        fix += 1
    if road[s] == False: 
        fix -= 1

print(min_fix)

문제풀이

1. n, k, b를 각각 입력받는다.

2. 길이가 n+1인 리스트 road를 생성하고, 모든 신호등을 정상(True)로 초기화한다.

3. b번 반복하면서 고장난 신호등의 위치를 입력받고 고장으로 표시한다.

4. 1부터 k까지 확인하며 고쳐야 하는 신호등의 개수를 fix에 더해준다.

5. while 반복문을 통해 e를 증가시켜 고쳐야 할 신호등 수를 계산한다. e에 위치한 신호등이 고장난 상태라면 fix를 증가하고, s에 위치한 신호등이 고장난 상태라면 fix를 감소시킨다.

6. s와 e의 위치를 이동한다.

7. 고장난 신호등 수를 출력한다.