[백준 28325] 호숫가의 개미굴 (Gold 5)

문제

요약

n개의 방이 원형으로 늘어서 있다.
각 방에는 c(i)개의 쪽방이 나있다.
모든 방과 쪽방에는 한 마리의 개미만 들어갈 수 있다.
모든 방과 쪽방의 거리를 1 이상 유지해야 한다.
개미의 최댓값을 구하라

풀이

1. 내 풀이

개미가 방에 산다면, 양쪽을 빈방으로 만들어야 한다. 2의 비용이 들어간다고 하자. 쪽방의 경우에는, 쪽방과 연결된 방만 비우면 되므로 1/c(i)의 비용이 든다. 따라서 쪽방이 존재한다면, 모든 쪽방에 개미가 사는 것이 유리하다.

모든 쪽방에 개미가 산다고 가정한다. 쪽방과 연결된 방은 반드시 비워야 한다. 이를 기준으로 쪽방이 없는 방들의 개미 거주 여부를 결정한다. n개의 쪽방 없는 방이 늘어서 있다면 살 수 있는 개미의 최댓값은 (n + 1) // 2 이다.

이제 특수한 경우를 알아보자. 크게 신경써야 할 부분은, 모든 방의 쪽방의 개수가 1일때와, 모든 방이 쪽방을 가지지 않을 때다. 전자의 경우에는 거주 개미 최댓값은 방의 개수가 된다. 후자의 경우, 거주 개미의 최댓값은 n // 2가 된다.

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

cnt = 0
cur_zero = 0

if all(val == 1 for val in arr):
    cnt = n

elif all(val == 0 for val in arr):
    cnt = n // 2

else:
    first_zero = 0
    first = True

    for val in arr:
        if val == 0:
            if first:
                first_zero += 1
            else:
                cur_zero += 1
        else:
            if first:
                first = False
            cnt += val + (cur_zero + 1) // 2
            cur_zero = 0

    cnt += (cur_zero + first_zero + 1) // 2

print(cnt)

[백준 28325] 호숫가의 개미굴 (Gold 5)

문제

요약

분류

풀이

1. 내 풀이