아이디어

• 구하고자 하는 '각 그룹의 합의 최솟값'을 이진탐색으로 구해보려 한다.
• 범위는 0부터 어떤 큰 수까지 시작한다.
• 이진 탐색의 mid 값을 최솟값으로 해서 만들 수 있는 그룹의 수를 구한다.
  • 만약 그룹의 수가 K보다 많다면, 더 큰 최솟값을 가지도록 나눌 수 있었다는 뜻이므로 범위를 오른쪽으로 좁힌다.
  • 만약 그룹의 수가 K보다 작다면, 최솟값이 더 작아야 K개로 나눌 수 있다는 뜻이므로 범위를 왼쪽으로 좁힌다.
  • 만약 그룹의 수가 정확히 K라면, 그룹의 수가 K가 되는 mid 중에서도 큰 최솟값을 찾아야 하므로 범위를 오른쪽으로 좁힌다.
• 탐색이 끝나면 l > r 상태인데, cnt == K인 경우에 r이 유지되므로 r이 정답

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, K, xSum;
	static int[] x;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		K = Integer.parseInt(tk.nextToken());
		
		x = new int[N];
		tk = new StringTokenizer(rd.readLine());
		for (int i=0; i<N; i++) {
			x[i] = Integer.parseInt(tk.nextToken());
			xSum += x[i];
		}
		
		// 최소 점수(정답)을 몇으로 해야 하나?
		int l = 0;
		int r = xSum;
		
		while (l <= r) {
			int m = (l + r) / 2;
			
			int sum = 0;
			int cnt = 0;
			for (int i=0; i<N; i++) {
				sum += x[i];
				if (sum >= m) {
					cnt++;
					sum = 0;
				}
			}
			if (cnt >= K) l = m + 1;
			else r = m - 1;
		}
		
		// cnt == K인 것 중에 가장 큰 것이므로 r을 ㄱ
		System.out.println(r);
	}
}

메모리 및 시간

• 메모리: 22996 KB
• 시간: 288 ms

리뷰

• 이 문제가 이분 탐색임을 몰랐다면 이 문제에 접근할 수 있었을까?