[백준] 28325 - 호숫가의 개미

문제 링크

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

문제 요약

KOI 호숫가에 여러 개미굴이 원형으로 배치되어 있으며, 각 개미굴은 1번 방부터 N번 방까지 번호가 매겨져 있습니다. 각 방은 인접한 방과 연결되어 있고, 일부 방에는 하나 이상의 쪽방이 달려 있습니다. 쪽방은 i번 방과만 연결되어 있으며, 다른 방과는 연결되어 있지 않습니다.

개미굴의 각 방과 쪽방에는 최대 한 마리의 개미만 살 수 있으며, 서로 인접한 두 곳(방 또는 쪽방)에 동시에 개미가 살면 불편함을 느낍니다. 따라서, 직접 연결된 두 곳에는 동시에 개미가 살 수 없고, 두 곳 중 하나에만 개미를 배치해야 합니다. 이 조건 하에서 최대한 많은 개미를 배치할 수 있도록 프로그램을 작성하는 것이 목표입니다.

푼 방법

 

• 쪽방이 있는 방을 우선 처리:
  • 쪽방이 있는 경우, 개미들을 모두 쪽방에 배치하는것이 무조건 이득이므로 쪽방에 개미를 모두 배치합니다.
• 남은 방에 최대한 많은 개미 배치:
  • 쪽방이 없는 방이나 이미 개미가 배치되지 않은 방에 대해 남은 방들을 처리합니다. 즉, 가능한 한 많이 개미를 배치할 수 있는 방부터 개미를 배치해 나갑니다.
  • 인접한 방에 개미가 배치되지 않은 상태에서만 그 방에 개미를 배치할 수 있도록 주의하면서, 전체 방을 순회합니다.
• 최종 개미 수 계산:
  • 모든 쪽방 수과 쪽방이 없는 방들을 2로 나눈 몫이 답이 됩니다.

 

정답 코드

import sys
n = int(sys.stdin.readline().rstrip())
rooms = list(map(int, sys.stdin.readline().split()))

chk = [True] * n
result = sum(rooms)

if result == 0:
    print(n//2)
    exit()

for i in range(n):
    if rooms[i] > 0:
        chk[i] = False

idx = 0
for i in range(len(chk)):
    if chk[i] == False:
        idx = i
        break

chk = chk[idx+1:]+chk[:idx+1]
# print(chk)
temp = 0
for i in range(n):
    if chk[i] == False:
        result += (temp+1)//2
        temp =0
    else:
        temp+=1

print(result)

배웠던 부분

• 첫 번째 방과 마지막 방이 쪽방이 없는 경우를 처리하는데 오래 걸렸었는데
• 가장 처음 쪽방 있는 굴 이전의 개수만큼 굴을 저장하는 리스트 뒤에 붙여주면 해결할 수 있다.
  
  • = 시작을 항상 쪽방이 있는 굴로 시작하면 된다.