[BaekJoon] 2613 숫자구슬 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M, left, right;
    static int[] marbles;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
        left = right = 0;
        marbles = new int[N];

        for(int idx = 0; idx < N; idx++) {
            marbles[idx] = scanner.nextInt();

            left = Math.max(left, marbles[idx]);
            right += marbles[idx];
        }
    }

    static void solution() {
        StringBuilder sb = new StringBuilder();

        int maxGroupSum = binarySearch();
        sb.append(maxGroupSum).append('\n');

        getEachGroupMarblesNum(maxGroupSum, sb);
        System.out.println(sb);
    }

    static void getEachGroupMarblesNum(int maxGroupSum, StringBuilder sb) {
        int count = 0, sum = 0;
        for(int idx = 0; idx < N; idx++) {
            sum += marbles[idx];
            if(sum > maxGroupSum) {
                M--;
                sum = marbles[idx];
                sb.append(count).append(" ");
                count = 1;
            } else count++;

            // 남은 구슬 수와 남은 그룹의 수와 같다면 각 구슬이 하나의 그룹을 이루니 여기서 break
            if(M == N - idx) break;
        }

        while(M-- > 0) {
            sb.append(count).append(" ");
            count = 1;
        }
    }

    static int binarySearch() {
        while(left <= right) {
            int mid = (left + right) / 2;
            int groupNum = getGroupNum(mid);

            if(groupNum > M) left = mid + 1;
            else right = mid - 1;
        }

        return left;
    }

    static int getGroupNum(int maxGroupSum) {
        int sum = 0, count = 1;
        for(int idx = 0; idx < N; idx++) {
            sum += marbles[idx];
            if(sum > maxGroupSum) {
                count++;
                sum = marbles[idx];
            }
        }

        return count;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 이분탐색을 통해 M개의 그룹으로 나눌 때의 그룹의 합 중 최댓값을 구합니다.
  • 그룹의 합을 구하기 위해 최솟값인 0과 최댓값인 모든 구슬의 합을 초기값으로 놓고 이분탐색을 진행합니다.
  • 이분탐색 시에 나오는 (left + right) / 2 값을 그룹의 합의 최댓값으로 잡고 그룹의 수를 구해본 후에 그룹의 수가 M보다 크다면 그룹의 합의 최댓값을 늘려야하기 때문에 left의 값을 mid + 1로 하고, 그렇지 않다면 그룹의 합의 최댓값을 줄여야하기 때문에 right의 값을 mid - 1로 합니다.
    • M과 같은 경우에는 우리는 그룹의 합의 최댓값 중 최솟값을 구하고자 하기 때문에 그룹의 합의 최댓값을 줄여야하므로 right의 값을 mid - 1로 합니다.
• 이분탐색을 통해 그룹의 합의 최댓값을 구했다면 그 값을 이용하여 가장 앞의 구슬에서부터 그룹에 속하는 구슬의 개수를 구해나갑니다.
  • 한 그룹에는 그룹의 합의 최댓값 이상의 구슬들이 들어갈 수 없기 때문에 이를 이용하여 한 그룹에 있는 구슬들의 합이 그룹의 합의 최댓값을 넘지 않는 선에서 한 그룹에 구슬들을 계속 채워나가고 넘게 된다면 그 구슬부터 새로운 그룹을 만듭니다.