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. 하나씩 옆으로 밀면서 첫번째 요소를 빼고 다음 요소를 더하며 최소값 업데이트
'Koala - 17기 > 코딩테스트 심화 스터디' 카테고리의 다른 글
[백준/Python] 2003번: 수들의 합 2 (0) | 2025.01.26 |
---|---|
[BOJ/Python3] 2842번 : 집배원 한상덕 (0) | 2025.01.26 |
[백준/C++] 2531번: 회전 초밥 (0) | 2025.01.24 |
[백준/Python] 1700번: 멀티탭 스케줄링 (0) | 2025.01.19 |
[백준/Java] 1890. 점프 (0) | 2025.01.19 |