오늘의 회고

소마 코테를 봤을 때도 그렇고 내가 그리디 알고리즘 로직을 많이 안다뤄봤다고 생각해서 그리디 문제를 풀었다. 앞으로 당분간 그리디 문제 풀 예정이다!
오늘은 문제 제목부터 강렬한 소가 길을 건너간 이유5를 풀었다.

풀이

n의 최대 개수 100000개이고 시간제한도 2초라 넉넉해서 브루트포스로 모든 경우의 수를 다 탐색했다.

1. broken 리스트로 고장난 건 True로 갱신
2. idx 0부터 K개, 1부터 K개, 2부터 K개 이런 식으로 for문
3. for문 안에서 고장난 신호등(broken_cnt), 연속 몇 번째 신호등(traffic)인지 변수로 따로 관리
4. 최소 몇 개의 신호등을 고쳐야 하는지 리스트에 넣어서 맨 마지막에 리스트의 최솟값을 출력

정답 코드

오로지 혼자 힘으로 풀었다!!

import sys
input = sys.stdin.readline

N, K, B = map(int, input().split())
broken = [False]*(N+1)

for i in range(B):
    broken[int(input())] = True # 고장

answer = []
for i in range(1, N+2-K):
    broken_cnt = 0
    traffic = 0
    for j in range(i, N+1):
        if broken[j]: # 고장
            broken_cnt += 1
        traffic += 1
        if traffic == K:
            break
    answer.append(broken_cnt)
print(min(answer))