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

문제

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

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

---

문제 요약

일자형 도로 위의 횡단 보도 개수 N와 고장난 신호등 B개의 정보를 입력 받는다.
정상적으로 작동하는 신호등이 연속으로 K개 있도록 만들기 위해 최소로 필요한 수리할 신호등 개수를 출력한다.

---

코드 (누적 합)

N, K, B = map(int, input().split())
# 횡단보도 개수 N, 연속하는 신호등 개수 K, 고장난 신호등 개수 B
 
arr = [0] * (N + 1)
# arr[i]는 i에 존재하는 신호등 상태 (고장이면 1, 아니면 0)

for i in range(B):
    arr[int(input())] = 1
    # 고장난 신호등을 1로 표시

s = []
# s[i]는 0부터 i까지 고장난 신호등의 개수
cnt = 0
for i in range(N + 1):
    cnt += arr[i]
    s.append(cnt)

answer = B
# 연속한 신호등 개수가 K개가 되도록 하는 고쳐야 하는 신호등의 최소 개수
# 초기 값은 모두 고쳐야 할 때

for i in range(N + 1 - K):
# 길이가 K인 모든 구간을 탐색
    answer = min(answer, s[i + K] - s[i])
    # s[i + K] - s[i]는 i부터 i + K까지의 고장난 신호등 개수

print(answer)

---

코드 설명

1. 0부터 i까지 고장난 신호등의 개수를 저장하는 배열을 생성한다.
 
2. 길이가 K인 횡단 보도의 모든 구간 (i ~ i + K) 을 탐색하여 고장난 신호등이 가장 적은 구간을 찾는다.

---

코드 (슬라이딩 윈도우)

N, K, B = map(int, input().split())
# 횡단보도 개수 N, 연속하는 신호등 개수 K, 고장난 신호등 개수 B
 
arr = [0] * (N + 1)
# arr[i]는 i에 존재하는 신호등 상태 (고장이면 1, 아니면 0)

for i in range(B):
    arr[int(input())] = 1
    # 고장난 신호등을 1로 표시

s, e = 1, K
# 연속하는 횡단보도 구간의 시작 위치 s, 끝 위치 e

total = sum(arr[s:e + 1]) # 현재 구간 내 존재하는 고장난 신호등 개수

answer = B

while e < N:
    # 이동할 시작 지점이 고장난 신호등(1) 이면 감소. 아니면(0) 감소 X
    total -= arr[s]

    # 구간 이동
    e += 1
    s += 1

    # 추가된 끝 지점이 고장난 신호등(1) 이면 추가. 아니면(0) 추가 X
    total += arr[e]

    answer = min(total, answer)
    #시작지점이 고장난 신호등 이었다면 1을 빼주고 추가되는 인덱스가 고장난 신호등이라면 1을 더해주면 된다.
print(answer)

---

코드 설명

위 코드처럼 슬라이딩 윈도우 풀이로도 풀 수 있다.
 
구간의 시작 지점 s와 끝 지점 e를 이동시키며 변화하는 값을 갱신해준다.

---

블로그 코드 참고

https://gona.tistory.com/17