[Java] 백준 2613번: 숫자구슬

[문제 바로 가기] - 숫자구슬

📌 유형 : 매개 변수 탐색

이분 탐색 문제를 오랜만에 풀었을 뿐더러 이 문제는 최댓값을 구하고 나서도 나눠진 그룹을 구해야하므로 생각보다 복잡했다.

개인적으로 깊게 생각하게 돼서 좋은 문제인 것 같다.

💡 아이디어

먼저 매개 변수 탐색으로 각 그룹의 합 중 최댓값이 최소가 되는 값을 구한다.

• left : 구슬 중 가장 큰 값
• right : 모든 구슬 값의 합

countBeadGroup 함수

• sum, 즉 각 그룹의 합이 mid보다 작거나 같을 경우 구슬을 계속 더하고, mid를 초과할 경우에는 새 그룹을 만들어(group++ 부분) sum을 초기화한다.

binarySearch 함수

• 이 과정을 거쳐 나온 group이 M을 초과할 경우에는 mid를 높여야 하므로 left = mid + 1, M보다 작을 경우에는 right = mid - 1를 한다.
• 이 과정을 반복하면서 left가 최적의 최댓값이 되므로 먼저 StringBuffer에 값을 넣어준다.

★ printGroupSize 함수

• 가장 중요한 부분으로 구슬 그룹을 실제로 어떻게 나눌지 정하는 함수다.
• groupSum에 각 구슬의 값들을 더하면서 left를 초과할 경우, 즉 구슬의 합이 최댓값을 넘어갈 경우

	1. 만들어야 하는 그룹의 수인 `M--`
	2. 구슬의 합 `groupSum` 초기화
    3. 현재 그룹의 구슬 수 출력
    4. 구슬 수 `beadsInGroup` 초기화

• groupSum이 left를 초과하지 않을 경우 beadsInGroup++

• 이 과정에서 남은 그룹 수가 남은 구슬의 수와 같을 경우 break
  - 구슬들을 모두 그룹에 할당해야 하기 때문에 하나씩 할당해주기 위해서

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

• 위의 반복문에서 저장해두었던 beadsInGroup을 StringBuffer에 저장하고, 이후에는 1개씩 할당해준다.

---

풀이

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

/**
 * 백준 2613번 숫자구슬
 * - 매개 변수 탐색
 */

public class Main {
	public static int N, M, left, right;
	public static int[] num;
	public static StringBuffer sb = new StringBuffer();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		
		left = 0;
		right = 0;
	
		num = new int[N];
		for (int i = 0; i < N; i++) {
			num[i] = Integer.parseInt(st.nextToken());
			
			left = Math.max(left, num[i]); // 구슬 중 가장 큰 값
			right += num[i]; // 모든 구슬 값의 합
		}
		
		binarySearch(); // 매개 변수 탐색
		printGroupSize();
	}
	
	public static void binarySearch() {
		while (left <= right) {
			int mid = left + (right - left) / 2;
		
			int group = countBeadGroup(mid);
			
			if (group > M) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		
		sb.append(left + "\n");
	}
	
	public static int countBeadGroup(int mid) {
		int group = 1;
		int sum = 0;
		
		for (int n : num) {
			sum += n;
			
			if (sum > mid) {
				group++;
				sum = n;
			}
		}
		
		return group;
	}
	
	public static void printGroupSize() {
		int beadsInGroup = 0;
		int groupSum = 0;
		
		for (int i = 0; i < N; i++) {
			groupSum += num[i];
			
			if (groupSum > left) { // 구슬의 합이 최댓값을 넘어갈 경우
				M--; // 그룹이 만들어졌으므로 M--
				groupSum = num[i]; // 합 초기화
				sb.append(beadsInGroup + " "); // 현재 그룹의 구슬 수 출력
				beadsInGroup = 1; // 구슬 수 초기화
			} else beadsInGroup++;
			
			if (M == N - i) break; // 남은 그룹 수 == 남은 구슬 수
		}
		
		while (M-- > 0) {
			sb.append(beadsInGroup + " ");
			beadsInGroup = 1;
		}
		
		System.out.println(sb.toString());
	}
}