아이디어

• 풀이가 떠오르지 않을 때는 완전탐색부터 고려해보자.
  • $K$를 $\max(A)$부터 $\sum A$까지 모두 탐색하면 조건을 만족하는 $K$의 최솟값을 찾을 수 있지만, 시간복잡도가 $O(N \times \sum A)$이 되서 시간 내 풀이가 어렵다. ($\sum A$은 10억 이하)
• $K$가 작아질 수록 인출 횟수가 커지는 성질이 있다.
• 인출 횟수가 $M$ 이하가 되도록 하는 값 중 최솟값을 찾으면 된다.
• 이분 탐색을 이용하여 답이 되는 $K$를 찾는다.
  • 범위의 중간값을 $K$로 하여 시뮬레이션 하고 횟수를 얻어 $M$보다 작은지 본다.
  • $M$ 이하라면 $K$를 더 줄일 가능성이 있으므로 범위를 왼쪽으로 옮긴다.
  • $M$보다 크다면 이 이하의 $K$에 대해서는 답이 될 가능성이 없으므로 범위를 오른쪽으로 옮긴다.

코드

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, M, max, sum, ans, cnt, left;
	static int[] A;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		M = Integer.parseInt(tk.nextToken());
		
		A = new int[N];
		for (int i=0; i<N; i++) {
			A[i] = Integer.parseInt(rd.readLine());
			max = Math.max(max, A[i]);
			sum += A[i];
		}
		
		int l = max;
		int r = sum;
		int m = 0;
		while (l < r) {
			m = (l + r) / 2;
			
			cnt = 0;
			left = 0;
			for (int i=0; i<N; i++) {
				if (left < A[i]) {
					left = m;
					cnt++;
				}
				left -= A[i];
			}
			
			if (cnt > M) {
				l = m + 1;
			}
			else {
				r = m;
			}
		}
		
		System.out.println(l);
	}
}

메모리 및 시간

• 메모리: 23140 KB
• 시간: 272 ms

리뷰

• parametric binary search의 문제 유형이 눈에 들어오는 것 같다. (~~를 만족하는 최대/최솟값)