[백준 / Java] 2613번: 숫자구슬 (골드2)

문제 풀이 날짜: 2023.09.05
포스트 작성일: 2023.09.11

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 2613번: 숫자구슬 (골드2)

 

키워드

이분 탐색, 매개변수 탐색

 

풀이 접근법

• 이 문제에서 이분 탐색으로 구하는 대상은 각 구슬의 경계를 나누는 경계값이 아니라 구슬의 합이다.
  • left는 전체 구슬 중 가장 큰 값 한 가지(원소가 1개인 집합)이다.
  • right는 전체 구슬의 합(모든 원소를 포함한 집합)이다.
  • 형성해야 하는 그룹의 수와 현재까지 형성된 그룹의 수를 비교해가며 이분탐색 범위를 늘리거나 줄여간다.

 

코드

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

public class Main {

	private static int N;
	private static int M;

	private static int[] beads;
	
	private static StringBuilder sb = new StringBuilder();
	
	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());
		
		beads = new int[N];

		int start = 0;
		int end = 0;
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < N; i++) {
			beads[i] = Integer.parseInt(st.nextToken());
						
			start = Math.max(beads[i], start);
			end += beads[i];
		}

		int answer = Integer.MAX_VALUE;
		
		int mid = 0;
		//parametric search
		while(start <= end) {
			mid = (start + end) / 2;
			
			if(isValidGroup(mid)) { //그룹의 수가 적다면
				end = mid - 1; //최댓값을 더 작게 잡는다.
				answer = Math.min(answer, mid);
			} else { //그룹의 수가 많다면
				start = mid + 1; //최댓값을 더 크게 잡는다.
			}
		}
		
		sb.append(answer).append("\n"); 
		
		printGroup(answer, M);
		
		System.out.println(sb);
	}

	private static void printGroup(int mid, int target) {
		int sum = 0;
		int count = 0;
		
		for(int i = 0; i < beads.length; i++) {
			sum += beads[i];
			
			if(sum > mid) {
				sum = beads[i]; //새로운 구간부터 다시 부분합을 구한다.
				//한 그룹을 모두 묶었으므로 append 해준다.
				sb.append(count).append(" ");
				
				target -= 1; //앞으로 뽑을 그룹 수 감소
				count = 0;
			}
			count += 1;
			
			//앞으로 구할 그룹의 수와 잔여 구슬의 수가 일치한다면 break
			if(N - i == target) break;
		}
		
		//다른 그룹을 모두 묶었는데 target이 0이 아니라면
		while(target-- > 0) { //1개짜리 그룹을 append 해준다.
			sb.append(count).append(" ");
			count = 1;
		}
	}

	private static boolean isValidGroup(int mid) {
		int sum = 0;
		int groupCount = 1;
		
		for(int i = 0; i < beads.length; i++) {
			sum += beads[i];
			
			if(sum > mid) {
				sum = beads[i]; //새로운 구간부터 다시 부분합을 구한다.
				groupCount++;
			}
		}
		
		return (M >= groupCount);
	}

}

---

매개변수 탐색은 아직 익숙하지 않았고, 각 구슬의 집합을 나누는 경계면을 골라야 한다고 생각했었기 때문에 풀이를 구상하기 어려웠다. 따라서 다른 분들의 풀이를 참고하였으며, 이분 탐색에서는 탐색의 대상을 올바르게 선정하는 것이 특히나 중요해보이므로 주의할 필요가 있겠다.

 

참고한 링크

https://zoosso.tistory.com/415
https://everenew.tistory.com/66