백준 12982 - 공 포장하기 2 (Python)

문제 정보

• https://www.acmicpc.net/problem/12982
• 그리디, 브루트포스, 정렬

---

문제 정리

K개의 색의 공이 여러 개 주어진다. 한 박스에는 공을 최대 K개까지 담을 수 있고, 박스 안의 공은 모두 같은 색이거나 모두 다른 색이어야 한다. 이 조건을 만족하면서 모든 공을 포장하기 위해 필요한 박스 개수의 최소값을 구하는 문제이다.

---

풀이

박스 용량이 K이므로, 박스를 꽉 채울수록 필요한 박스 수가 줄어들게 된다.
특히 같은 색 공을 K개씩 담는 것은 무조건 이득이고, 다른 방식으로 이 K개를 더 적은 박스로 담을 수 없다.

1. 같은 색 공을 K개씩 최대한 포장.
2. 남는 잔여 공들을 모아 정렬.
3. 잔여 공을 같은 색 박스와 다른 색 박스로 나누어 최소화.
   • 남는 공을 처리하는 방법은 크게 두 가지이다. (어떤 색 공을 전부 하나의 상자에 담기)와 (남은 모든 색 공을 하나씩 상자에 담기)이다.
   • 어디까지 같은 색 박스로 묶어야 최적인지 모르므로, [0, i-1]의 상자에 대해선 같은 색 공으로만 구성되도록, [i, len(ball))에 대해선 다른 색 공으로만 구성되도록 한다. 이 과정을 [1, len(ball)) 값에 대해 모두 시도해 최소값을 찾으면 된다.

3번 과정을 글로 쓰려니까 좀 어색한데, 아래 코드를 보면 이해가 될 것이다.

2번까지는 어떻게 생각해냈는데 3번을 못 떠올려서 인터넷을 좀 참고했다...

---

코드

# 백준 12982

import io

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


def solve(K, X):
    box = 0

    # 같은 색 공을 K개씩 묶고 남은 공 저장 
    ball = []
    for i in range(K):
        box += X[i] // K
        left = X[i] % K
        if left > 0:
            ball.append(left)

    if len(ball) == 0:
        return box

    # [0, i-1]까지는 같은 색끼리, [i, len(ball)-1]까지는 다른 색끼리 박스에 담기
    ball.sort(reverse=True)
    total = len(ball)
    for i in range(len(ball)):
        total = min(total, i+ball[i])

    return box + total


def main():
    K = int(input())
    X = list(map(int, input().split()))
    print(solve(K, X))


main()