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

안녕하세요! 오늘은 백준의 14465번 문제인 “소가 길을 건너간 이유 5” 문제를 함께 풀어보겠습니다. 이 문제는 연속된 신호등 구간에서 고장난 신호등의 수를 최소화하는 문제입니다. 함께 문제를 해결해보도록 하죠!

 

1. 문제 설명

1) 신호등의 개수(N), 연속된 신호등의 개수(K), 고장난 신호등의 개수(B)가 주어집니다.

2) 고장난 신호등의 위치가 주어집니다.

3) K개의 연속된 신호등 구간에서 고장난 신호등의 수를 최소화해야 합니다.

 

문제URL : https://www.acmicpc.net/problem/14465

 

2. 접근법

1) 입력받기: 신호등의 개수, 연속된 신호등의 개수, 고장난 신호등의 개수와 고장난 신호등의 위치를 입력받습니다.

2) 누적합 배열 생성: 고장난 신호등의 위치를 반영한 후, 누적합 배열을 만듭니다.

3) 최소 고장난 신호등 수 계산: 연속된 K개의 신호등 구간에서 고장난 신호등의 수를 계산하여 최소값을 구합니다.

 

3. 정답 코드

import sys
input = sys.stdin.readline

# N: 신호등의 개수, K: 연속된 신호등의 개수, B: 고장난 신호등의 개수
N, K, B = map(int ,input().split())

# 신호등 상태를 저장할 리스트 (0: 정상, 1: 고장)
sinho = [0] * N

# 누적합을 저장할 리스트 (0번 인덱스는 0으로 초기화)
psum = [0] * (N + 1)

# 고장난 신호등의 위치를 입력받아 리스트에 반영
for _ in range(B):
    num = int(input())
    sinho[num-1] = 1  # 고장난 신호등 위치를 1로 표시

# 누적합 배열 생성 (1번 인덱스부터 시작)
for i in range(1, N+1):
    psum[i] = psum[i-1] + sinho[i-1]

# 고쳐야 하는 신호등의 개수를 저장할 리스트
ans = []

# K개의 연속된 구간에서 고장난 신호등의 수를 계산
for i in range(K, N+1):
    ans.append(psum[i] - psum[i-K])

# 가장 작은 고장난 신호등의 수를 출력
print(min(ans))

 

4. 코드 설명

1) 입력받는 부분

 

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 첫 번째 줄에서 N(신호등의 개수), K(연속된 신호등의 개수), B(고장난 신호등의 개수)를 입력받습니다.

• 다음 줄에서 고장난 신호등의 위치를 입력받아 sinho 리스트에 반영합니다.

 

2) 누적합 배열 생성

 

• sinho 리스트에 고장난 신호등의 위치를 1로 표시합니다.

• psum 리스트를 생성하여 각 인덱스까지의 고장난 신호등의 수를 저장합니다.

 

3) 최소 고장난 신호등 수 계산

 

• 연속된 K개의 신호등 구간에서 고장난 신호등의 수를 계산하여 ans 리스트에 저장합니다.

• ans 리스트에서 가장 작은 값을 출력하여, 고쳐야 하는 최소 신호등의 수를 구합니다.

 

*****

예시로 정답코드 설명

• 신호등의 개수(N): 10

• 연속된 신호등의 개수(K): 5

• 고장난 신호등의 개수(B): 3

• 고장난 신호등의 위치: 2, 4, 7

 

신호등 초기 상태: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

고장난 신호등의 위치 반영

고장난 신호등 상태: [0, 1, 0, 1, 0, 0, 1, 0, 0, 0]

 

누적합 배열 생성

i=1: psum[1] = psum[0] + sinho[0] = 0 + 0 = 0

i=2: psum[2] = psum[1] + sinho[1] = 0 + 1 = 1

i=3: psum[3] = psum[2] + sinho[2] = 1 + 0 = 1

i=4: psum[4] = psum[3] + sinho[3] = 1 + 1 = 2

i=5: psum[5] = psum[4] + sinho[4] = 2 + 0 = 2

i=6: psum[6] = psum[5] + sinho[5] = 2 + 0 = 2

i=7: psum[7] = psum[6] + sinho[6] = 2 + 1 = 3

i=8: psum[8] = psum[7] + sinho[7] = 3 + 0 = 3

i=9: psum[9] = psum[8] + sinho[8] = 3 + 0 = 3

i=10: psum[10] = psum[9] + sinho[9] = 3 + 0 = 3

 

누적합 배열

psum: [0, 0, 1, 1, 2, 2, 2, 3, 3, 3, 3]

 

최소 고장난 신호등 수 계산

K개의 연속된 구간에서 고장난 신호등의 수 계산

i=5: ans.append(psum[5] - psum[0]) = 2 - 0 = 2

i=6: ans.append(psum[6] - psum[1]) = 2 - 0 = 2

i=7: ans.append(psum[7] - psum[2]) = 3 - 1 = 2

i=8: ans.append(psum[8] - psum[3]) = 3 - 1 = 2

i=9: ans.append(psum[9] - psum[4]) = 3 - 2 = 1

i=10: ans.append(psum[10] - psum[5]) = 3 - 2 = 1

 

ans 리스트

ans: [2, 2, 2, 2, 1, 1]

*****

5. Github으로 확인

 

coTest/BOJ/BOJ01_06_02_14465.py at main · pcy4196/coTest