[백준 28325] 2023 정올 "호숫가의 개미굴"

문제 출처 : https://www.acmicpc.net/problem/28325

28325번: 호숫가의 개미굴

이 문제는 2023년 정보올림피아드 2차 대회 초등부 3번, 중등부 2번 문제입니다.

이 문제를 풀기 위해서 생각해야 하는 부분을 알아보겠습니다.

쪽방 사용

개미굴에 쪽방이 있다면 쪽방을 이용하는 것이 최선 입니다.

그림과 같이 여러 개미굴이 있는 곳의 일부를 보도록 하겠습니다. 2번 개미굴에 쪽방이 하나 연결되어 있습니다. 쪽방인 4번을 선택하면 2번에는 더이상 개미가 들어올 수 없습니다. 대신 1번과 3번에 개미가 들어올 수 있습니다.

하지만 반대로 2번을 선택하면 2번을 제외한 모든 곳에 개미가 들어올 수 없습니다.

따라서 우리는 쪽방이 있다면 무조건 쪽방을 사용하는 것이 유리하다는 것을 알게 되었습니다. 문제는 쪽방이 없는 개미굴을 어떻게 할 것인가 입니다.

개미굴 구하기

모든 개미굴에 쪽방이 있다면 쪽방의 개수가 답이 됩니다. 하지만 일반적인 개미굴에는 쪽방이 있을수도 있고, 없을 수도 있습니다. 쪽방이 없는 개미굴은 계산을 통해 개미가 몇마리나 들어갈 수 있는지 확인해야 합니다. 그럼 여러 케이스에 대해 하나씩 해결해 보겠습니다.

모든 쪽방이 비었을 때

쪽방이 하나도 없는 경우 한 칸씩 비워야 하기 때문에 1/2 이상은 들어갈 수 없을 것 같습니다. 여기서 기억해야 하는 부분은 개미굴의 시작과 끝은 연결되어 있다는 것입니다. 3개의 개미굴이 있다면 단 한마리만 들어갈 수 있습니다.

1번 개미굴을 사용하고, 2번을 건너 뛰고 3번을 선택해도 결국 1번과 3번이 이어져 있습니다. 4개의 개미굴인 경우 최대 2마리가 들어갈 수 있습니다. 5마리일때는 최대 2마리가 들어갈 수 있습니다.

결국 개미굴이 홀수이던, 짝수이던 2로 나눈 몫 만큼의 개미가 살 수 있습니다.

쪽방이 없는 방 처리

쪽방이 있으면 그게 단 한마리라도 쪽방을 사용합니다. 문제는 쪽방이 없는 방을 어떻게 처리 하느냐 입니다. 이것도 하나하나 해결해 보겠습니다.

1번과 3번 개미굴에는 쪽방이 달려 있습니다. 쪽방인 4, 5번에 무조건 개미가 살게 하고 2번에 개미가 살면 최대로 살 수 있습니다.

다음으로 빈 방이 2개인 경우 입니다. 1번과 4번에 쪽방이 있으니 쪽방 5, 6번을 사용하고 빈 방인 2번이나 3번 중 하나를 선택해서 총 3마리가 살 수 있습니다.

빈 방이 3개인 경우 쪽방을 제외하고 2마리가 더 살 수 있습니다. 이렇게 한마리씩 늘려나가며 따져보면 (빈방의 개수 + 1) / 2 만큼 개미가 살 수 있습니다.

원형의 처음과 끝 처리

마지막으로 고려해야 하는 부분은 개미굴은 원통형으로 되어 있다는 것입니다. 즉 처음과 끝이 이어져 있습니다. 이 부분을 어떻게 처리해야 할지 고민을 해야 합니다.

이렇게 4번에 쪽방이 있는 경우 쪽방 8번에는 무조건 개미가 살고, 처음부터 빈방이 몇개인지 확인합니다. 1번 부터 3번까지 빈방이 있고 위에서 3개의 빈방에는 2마리가 살 수 있다고 했으니 2마리, 5번 부터 7번까지도 앞의 계산과 마찬가지로 2마리라고 하여 총 1 + 2 + 2로 5마리가 살 수 있다고 하면 틀리게 됩니다. 1번과 7번은 연결되어 있기 때문에 따로 계산하면 안됩니다.

 

어떻게 연결되어 있는지 고민할 필요 없이 개미굴의 시작을 쪽방이 있는 개미굴로 바꾼다면 원형이기는 하지만 떨어져 있는 것과 다를바 없게 됩니다.

이렇게 기존 4번을 1번으로 바꾸면 1번을 제외하고 6개의 빈 방이 있고, 2로 나누어 3개의 개미가 더 살 수 있게 됩니다. 그래서 총 4마리가 살 수 있게 됩니다.

지금까지 알아본 내용을 직접 코드로 작성해 보겠습니다.

입력 받기

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

print(solve(arr))

개미굴의 수 N과 쪽방의 정보 arr을 입력 받습니다. solve라는 함수를 만들어 결과를 리턴하도록 하겠습니다.

solve 함수 만들기

가장 먼저 쪽방이 하나도 없는 경우를 생각해 보겠습니다.

쪽방이 없는 경우

def solve(arr):
    total = sum(arr)
    if total == 0:        
        return N // 2

arr의 합이 0이라면 쪽방이 하나도 없다는 뜻입니다. 이 때는 전체 수를 2로 나누어 출력해주면 개미가 최대로 살 수 있는 개수를 알 수 있습니다.

시작점 이동

개미굴은 원형이기 때문에 시작점을 쪽방이 있는 곳으로 이동해야 된다고 했습니다. 그래야 원형임을 생각하지 않고 빈방의 개수로 계산할 수 있기 때문입니다.

    idx = 0
    for idx, a in enumerate(arr):
        if a:           
            break

    arr = arr[idx + 1:] + arr[:idx + 1]

arr을 돌면서 쪽방이 있는 곳의 인덱스값 idx를 알아내어 바로 빠져 나옵니다. 쪽방이 있는 idx를 기준으로 앞과 뒤를 잘라 이어 붙여 주었습니다.

빈 방 계산

    chk = [0] * N
    for i in range(N):
        if arr[i] or chk[i]:
            continue

        for j in range(i, N):
            if arr[j]:
                break

            chk[j] = 1
        total += (j - i + 1) // 2
    return total

chk는 계산을 한 빈방인지, 계산을 하지 않은 빈방인지 체크하는 것입니다. 계산이 된 빈 방은 chk[j]값이 1이 되어 다음 계산에서 빠지게 됩니다. 반복문을 돌면서 빈 방의 개수를 파악하고 (빈 방의 개수 + 1) // 2를 하여 total 값에 더해줍니다. 그 값이 최종 개미가 살 수 있는 최대의 수가 됩니다.

전체 코드

전체 코드를 다시한번 확인해 보겠습니다.

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

def solve(arr):
    total = sum(arr)
    if total == 0:        
        return N // 2
    
    idx = 0
    for idx, a in enumerate(arr):
        if a:           
            break
    
    arr = arr[idx + 1:] + arr[:idx + 1]

    chk = [0] * N

    for i in range(N):
        if arr[i] or chk[i]:
            continue

        for j in range(i, N):
            if arr[j]:
                break

            chk[j] = 1
        total += (j - i + 1) // 2
    return total 

print(solve(arr))