BOJ 2613) 숫자구슬

문제링크)

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

입력

첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 이하의 자연수이다.

출력

각 그룹의 합 중 최댓값이 최소가 되도록 M개의 그룹으로 나누었을 때 그 최댓값을 첫째 줄에 출력하고, 둘째 줄에는 각 그룹을 구성하는 구슬의 개수를 왼쪽부터 순서대로 출력한다. 구슬의 개수를 출력할 때는 사이에 한 칸의 공백을 둔다. 만약 그룹의 합의 최댓값이 최소가 되도록 하는 경우가 둘 이상이라면 그 중 하나만을 출력한다.

---

문제 풀이

문제 이해

제시된 문제의 입력 사이즈는 그렇게 크지 않다. N은 300 이하, M은 N보다 작으며, 구슬에 적힌 숫자는 100 이하이다.

무조건 구슬을 M개 그룹으로 나눈다고 했을 때, N개 구슬 사이사이 N-1개 공간에서 M-1개를 고른것과 같으므로

$(N-1)\choose(M-1)$ 가지 경우가 존재한다.

대표적으로 N = 300, M = 150 일 때, 11444906842896711259397675785618139767490572089618992588900 가지 경우가 있으므로 1초안에 찾을 수 없다.

접근 방법

숫자 구슬을 나누는 위치를 찾기보다는 가능한 숫자구슬 최댓값을 정해보는 것은 꽤 좋은 방법이다.

예를들어 최댓값이 200을 넘지 않도록 구슬을 M개 그룹으로 나눌 수 있는지를 보는 것이다.

정답인 최댓값이 K일 때, K개보다 작은 최댓값으로는 구슬을 M개 그룹으로 나눌 수 없고 더 많은 그룹이 생기게 된다.

왜냐하면 정답에서 요구하는 최댓값은 M개 그룹을 나눴을 때 생길 수 있는 최댓값 중 최소이기 때문이다.

또한 이 K보다 큰 최댓값 조건에서는 M개 이하의 그룹이 생길 수 있으나, M개보다 적은 그룹이 생기기도 한다. (예를들어, 1 1 1 1 1 그룹에서 M = 3일 때, 최댓값 제한을 100으로 한 경우)

숫자 구슬의 그룹은 오직 연속적으로 놓인 순서로만 모인다.

따라서 1번 구슬부터 시작하여 최댓값을 넘기지 않을 때 까지 구슬을 더해나가다가 더 많아지면, 해당 구슬 직전까지를 하나의 그룹으로 묶고 다음 구슬부터 새로 더해나간다.

이렇게 만들어진 그룹의 개수 등을 토대로 판단이 가능하다.

빠르게 최댓값 조건을 찾기.

위 조건은 특정값 K에 대해 2가지 케이스로 분할 할 수 있다.

1. 최댓값 조건 K로는 M개 그룹이하로 나눌 수 없음.
2. 최댓값 조건 K로 M개 그룹이하로 나눌 수 있음.

위 조건은 자연스럽게 정답인 K에 의해 더 작은 쪽과 더 큰 쪽으로 양분되며, 이를 기반으로 이진 탐색을 수행할 수 있다.

그룹의 최소 값인 1부터 최댓값인 30000 (300개 구슬, 구슬 번호가 모두 100, 그룹이 1개)를 경계로 두고 이진탐색을 수행한다.

덕분에 굉장히 빠르게 정답인 K로 접근이 가능하다.

엣지 케이스

단순히 최댓값을 찾는 것이라면 위의 방식으로 끝낼 수 있지만, 본 문제는 해당 조건일 때 각 그룹마다 구슬이 몇 개 포함되는지도 출력해야 한다.

즉, 구슬을 나누는 과정에서 실제로 그룹별로 구슬 개수를 카운트 해야 한다.

주의할 점은 정답인 K가 최댓값인 경우에 구슬을 M개 그룹으로 나눠도 정확히 M개 그룹에 구슬이 포함되지 않을 수 있다는 점이다.

8 8
100 200 100 100 100 100 100 100

위 입력에서 최댓값은 200 이다. 두번째 숫자인 200에 의해 자연스럽게 1 1 1 1 1 1 1 1 개 씩 그룹에 나눠질 것이라 생각하기 쉽지만,

최댓값이 200으로 고정된 순간, 200 이후 100과 그 옆에 100이 합해져 한 그룹에 최대 2개의 구슬이 포함되게 된다.

따라서 결과는 1 1 2 2 2 0 0 0 이 된다.

이 상태에서 구슬을 최댓값을 손상시키지 않으면서 M개 그룹들에 나눠줘야 한다.

가장 간단한 방법은 기준이 될 최댓값 그룹 A를 기준으로 좌, 우에서 구슬이 여유로운 그룹에서 1개씩 뽑아 A 전 후로 빈 그룹에 넣어주는 것이다.

단, A왼쪽 그룹에서 뽑은 구슬은 반드시 A보다 왼쪽 그룹에 포함되어야 한다. A왼쪽 그룹들에서 1개의 구슬이 사라지면, A에 포함되는 구슬들이 뽑아낸 개수만큼 앞으로 당겨지기 때문이다.

A 오른쪽 그룹도 마찬가지이다.

따라서 해당 로직을 잘 구현하면 이 문제는 정답을 맞출 수 있다.

기준이 될 A를 선정하는 것도 중요하다.

5 5
100 100 100 200 100

단순히 최댓값을 가지고 나누게 되면 위와 같은 입력에서 오답을 출력한다.

최댓값이 200일 때, 2 1 1 1로 나누어지게 된다.

기준 A를 개수가 2인 첫번째 그룹으로 두게 되면 나머지 그룹들은 구슬이 1개 씩 있기 때문에 M개 그룹으로 배분할 수가 없다.

따라서 같은 최댓값인 그룹들 중에서 가장 구슬이 적은 그룹을 찾고 해당 그룹을 기준으로 구슬을 분배해야 한다.

프로그램 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private static int N, M;
    private static int[] ary;
    private static int minMax = Integer.MAX_VALUE;
    private static int[] beads;
    private static int maxNumber = 0;

    public static void main(String[] args) throws Exception{
        init();
        solve();
        print();
    }

    public static void init() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tokens = br.readLine().split(" ");

        N = Integer.parseInt(tokens[0]);
        M = Integer.parseInt(tokens[1]);

        tokens = br.readLine().split(" ");
        ary = new int[N];
        for(int idx = 0; idx < N; idx++) {
            ary[idx] = Integer.parseInt(tokens[idx]);
            maxNumber = Math.max(maxNumber, ary[idx]);
        }
        beads = new int[M];
    }

    public static void solve() {
        int left = 0, right = 30000;
        int[] partialSums = new int[M];

        int[] candidateBeads = null;
        while(left < right) {
            int th = (left + right) / 2 + 1;
            int[] beadsBuffer = new int[M];
            int[] sums = split(beadsBuffer, th);
            if(sums != null) {
                right = th - 1;
                candidateBeads = beadsBuffer;
                partialSums = sums;
            } else {
                left = th;
            }
        }

        minMax = 0;
        int idx = 0;
        for(int i = 0; i < partialSums.length; i++) {
            minMax = Math.max(minMax, partialSums[i]);
            if (partialSums[idx] == partialSums[i]) {
                if (candidateBeads[idx] > candidateBeads[i]) idx = i;
            } else if (partialSums[idx] < partialSums[i]) idx = i;
        }
        fillGroups(candidateBeads, idx);
    }

    public static void fillGroups(int[] candidateBeads, int maxPartition) {
        int right = M - 1;
        while(candidateBeads[right] == 0) right--;
        if(right < M - 1) {
            int i = 0, j = 0;
            while(M - 1 - j != right - i) {
                if(i == maxPartition) {
                    beads[j++] = candidateBeads[i++];
                    continue;
                }
                beads[j++] = 1;
                candidateBeads[i]--;
                if(candidateBeads[i] == 0) i++;
            }

            while(i <= right) {
                beads[j++] = candidateBeads[i++];
            }
        } else {
            beads = candidateBeads;
        }
    }

    public static int[] split(int[] beadsBuffer, int threshold) {
        if(threshold < maxNumber) return null;

        int maxValue = 0;
        int bufferIdx = 0;
        int midSum = 0;
        int[] partialSums = new int[M];
        int pidx = 0;
        for(int i = 0; i < ary.length; i++) {
            if(midSum + ary[i] > threshold) {
                bufferIdx++;
                if(bufferIdx >= M) return null;
                partialSums[pidx++] = midSum;
                if(maxValue < midSum) {
                    maxValue = midSum;
                }
                midSum = 0;
            }
            midSum += ary[i];
            beadsBuffer[bufferIdx]++;
        }
        partialSums[pidx++] = midSum;
        return partialSums;
    }

    public static void print() {
        System.out.println(minMax);
        StringBuilder sb = new StringBuilder();
        for(int ans : beads) {
            sb.append(ans);
            sb.append(" ");
        }
        System.out.println(sb.toString());
    }
}