문제 링크: https://www.acmicpc.net/problem/28325

Thumbnail: Photo by mi_shots (Unsplash)

여러 시행 착오를 겪으며 풀었던 문제입니다. 백준 채점 서버에 문제가 있어 채점되는걸 오랫동안 기다렸습니다...ㅎㅎ

풀이

단계별로 계산하기

다음 과정으로 최대 개미의 수를 계산합니다:

• 먼저, 쪽방이 있는 경우는 쪽방에 개미를 채우고 본 방(쪽방이 연결된 방)을 비워둡니다.
• 이후, 쪽방이 없는 방을 각 방이 연속되는 구간 정보로 파악해 둡니다.
• 다음으로, 각 쪽방의 구간에 개미를 채웁니다.
  쪽방의 개수를 \(X\)라 할 때,
  • \(X\)가 홀수라면 \(X \div 2 + 1\)
  • \(X\)가 짝수라면 \(X \div 2\)

1) 쪽방에 개미를 모두 채우기

그냥 쪽방의 개수를 모두 더해주면 된다.

2) 쪽방이 없는 방이 연속되는 구간 파악하기

\(1 \cdots N\)을 반복하며, 쪽방의 개수가 0인 방이 어디에 위치하는지 구간 정보로 파악한다.

start = -1 # 현재 파악 중인 구간의 시작 위치
for i in range(N):
    if start == -1:
        if SUB_ROOMS[i] == 0:
            start = i
        else:
            CONTINUOUS_ZERO_SUBROOMS.append((start, i - 1))
            start = -1

if start != -1: # for문 종료 이후 처리되지 않은 구간에 대한 처리
    if SUB_ROOMS[0] == 0 and len(CONTINUOUS_ZERO_SUBROOMS) > 0: # N번 방의 쪽방도 0개인데 1번 방의 쪽방도 0개라면, 두 구간을 합친다.
        s, e = CONTINUOUS_ZERO_SUBROOMS[0]
        CONTINUOUS_ZERO_SUBROOMS.append((start, N + e))
        CONTINUOUS_ZERO_SUBROOMS.pop(0) # 첫 번째 쪽방은 마지막 쪽방과 연결되어 있으므로 제거
    else: # 그렇지 않은 경우는, 현재 파악중이던 구간을 새롭게 반영해준다.
        CONTINUOUS_ZERO_SUBROOMS.append((start, N - 1))

3) 쪽방이 없는 각 구간에 개미 채우기

이제 각 구간을 돌며 개미를 채워주면 됩니다.
구간의 길이를 기준으로 채울 수 있는 개미의 수를 정할 수 있습니다.

for s, e in CONTINUOUS_ZERO_SUBROOMS:
    if s == e:
        ants += 1
    else:
        length = e - s + 1
        ants += length // 2
        if length % 2 == 1:
            ants += 1

예외 처리

1) 쪽방이 하나도 없는 경우

이 경우, 앞서 쪽방이 없는 구간에 개미굴을 채우는 과정과 식을 조금 다르게 씁니다.
기본적으로 전체 방을 하나의 단일 구간으로 파악하고 계산하는데, 식은 다음과 같습니다.

이는 \(N\)번 방과 1번 방이 이어져 있기 때문입니다.

ants = sum(SUB_ROOMS)   # 먼저 모든 쪽방을 다 사용한다. (쪽방이 있는 본 방이 인접해도 쪽방끼리는 상관 없다.)
if ants == 0: # 쪽방이 하나도 없다면
    print((N - 1) // 2 + 1 if N % 2 == 0 else (N - 1) // 2)
    exit()

2) \(N\)번 방과 \(1\)번 방이 둘 다 쪽방이 없을 때

앞서 설명한 내용입니다만, 중요하니 다시 강조합니다.
이 경우, 마지막 구간과 첫 구간을 합쳐줘야 합니다. (개미굴은 원형 구조로, \(N\)번 방 이후에 다시 1번 방으로 이어집니다.)

전체 코드

input = open(0).readline
N = int(input().strip())
SUB_ROOMS = list(map(int, input().strip().split()))
CONTINUOUS_ZERO_SUBROOMS = []

ants = sum(SUB_ROOMS)   # 먼저 모든 쪽방을 다 사용한다. (쪽방이 있는 본 방이 인접해도 쪽방끼리는 상관 없다.)
if ants == 0: # 쪽방이 하나도 없다면
    print((N - 1) // 2 + 1 if N % 2 == 0 else (N - 1) // 2)
    exit()

start = -1
for i in range(N):
    if start == -1:
        if SUB_ROOMS[i] == 0:
            start = i
        else:
            CONTINUOUS_ZERO_SUBROOMS.append((start, i - 1))
            start = -1
if start != -1:
    if SUB_ROOMS[0] == 0 and len(CONTINUOUS_ZERO_SUBROOMS) > 0:
        s, e = CONTINUOUS_ZERO_SUBROOMS[0]
        CONTINUOUS_ZERO_SUBROOMS.append((start, N + e))
        CONTINUOUS_ZERO_SUBROOMS.pop(0) # 첫 번째 쪽방은 마지막 쪽방과 연결되어 있으므로 제거
    else:
        CONTINUOUS_ZERO_SUBROOMS.append((start, N - 1))

for s, e in CONTINUOUS_ZERO_SUBROOMS:
    if s == e:
        ants += 1
    else:
        length = e - s + 1
        ants += length // 2
        if length % 2 == 1:
            ants += 1

print(ants)