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

🌭 문제 설명

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

---

🍗 제한 사항

---

🎁 입출력 예시

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

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

---

😎 나의 풀이

N,K,B = list(map(int, input().split()))

check = [0] * N
for _ in range(B):
  id = int(input())
  check[id - 1] = 1 # 고장난 값이니까 1로 지정 정상값은 0
 
psum = [0] * N
psum[0] = check[0]

for i in range(1, N): # 누적합 계산
  psum[i] = psum[i - 1] + check[i]
  
need = []
for i in range(0, N - K + 1):
  if i == 0:
    num = psum[i + K - 1]
  else:
    num = psum[i + K - 1] - psum[i - 1]
  need.append(num)
print(min(need))

1. 누적 합을 이용해서 풀었다.
2. 고장난 신호등을 체크하기 위해 check배열을 만들고 1로 지정한다.
3. 누적 합 배열 psum을 선언하고 , check배열의 첫번째 값으로 초기화
4. 누적합을 계산해준다.
5. K개의 연속된 신호등 중에서 고장난 개수를 계산한다.
6. 첫 구간은 그대로 사용하고 , 다음 구간부터 구간 안에 고장 개수를 계산한다.
7. need 에 고장 개수인 num을 추가하고 여기서 min으로 최소 수리 개수를 출력한다.

---

🧵 다른 풀이

import sys
input = sys.stdin.readline

n, k, b = map(int,input().split()) # n은 도로 번호, k는 연속된 신호등, b 고장난 신호등 개수
light = [0]*(n+1)
for _ in range(b):
    light[int(input())] = 1

standard = sum(light[1:k+1])
min_fix = standard
for i in range(k+1,n+1):
    standard += light[i] - light[i-k]
    min_fix = min(standard, min_fix)

print(min_fix)

1. 슬라이딩 윈도우 방식이다.

---

• 슬라이딩 윈도우 방식은 처음 보는데 이것도 공부하면 좋을 것 같다.