[Python][백준/BOJ] 64655번 : 카약과 강풍

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

2891번: 카약과 강풍

 

내 코드

import sys
input = input
boat, S, R = map(int, input().split())
boat = [1 for _ in range(boat)]
df = list(map(int, input().split()))
good = list(map(int, input().split()))
for i in df:
    boat[i-1] -= 1
for i in good :
    boat[i-1] += 1
    
for i in range(len(boat)) :
    if boat[i] < 2 :
        continue
    if i > 0 and boat[i-1] < 1 :
        boat[i] -= 1
        boat[i-1] += 1
        continue
    if i + 1 < len(boat) and boat[i+1] < 1 :
        boat[i] -= 1
        boat[i+1] += 1

print(boat.count(0))

 

코드 리뷰

문제 자체는 어렵지 않았지만 반례를 생각하지 못해서 많이 헤맸던 문제이다.

앞뒤의 보트 상황을 살피는 것도 중요하지만, 현재 보트가 여분이 있으나 결함이 되었는지를 살피는 것도 중요하다.

 

보트가 1번부터 n번까지 있으면, n번까지의 보트를 1로 초기화한다.

for i in df:
    boat[i-1] -= 1
for i in good :
    boat[i-1] += 1

그리고 결함이 있는 보트는 -1을 해주고, 여분의 카약이 있는 보트는 +1을 한다.

한 바퀴를 다 돌면 전체 보트의 배열은 0(결함이 있는 보트), 1(결함이 있지만, 다행히 여분의 카약이 있던 보트), 2(여분의 카약이 있는 보트) 로 이루어질 것이다.

이 for문은 전체 초기화를 위해서 진행한 것도 있지만, '결함이 있지만, 다행히 여분의 카약이 있던 보트' 의 경우를 위해서도 존재한다.

for i in range(len(boat)) :
    if boat[i] < 2 :
        continue
    if i > 0 and boat[i-1] < 1 :
        boat[i] -= 1
        boat[i-1] += 1
        continue
    if i + 1 < len(boat) and boat[i+1] < 1 :
        boat[i] -= 1
        boat[i+1] += 1

그리고 boat 배열을 돌리면서 혹시 카약을 빌려줄 수 있는 상황이 되는지를 확인할 것이다.

1. 우선 값이 1이면 문제될 것 없으니 넘어간다.
2. 이미 0과 1인 보트는 넘어갔으니, 멈춘 지점은 여분이 있는 보트이다. i가 0이면 index_error가 발생하므로 i >0 인지 체크한다.
3. 다음 보트가 여분이 있다면 이전 보트에서 빌린다.

이렇게 다 돌렸는데도 0인 보트는 결함이 있지만, 빌리지 못하는 보트이므로 배열에서 0의 개수를 카운트해주면 된다.