아이디어

• 일단 예외처리: 모든 사람이 L만큼 먹어도 술이 부족(> T)하거나, R만큼 먹어도 술이 남으면(< T) S와 관계 없이 불가능한 경우
  • 이외의 경우에는 각자의 주량을 L[i]~R[i]에서 잘 조절하면 정확히 합이 T가 되도록 할 수 있다.
• S는 L의 최댓값과 R의 최댓값 범위 안에 있다.
• S를 적용하여 계산한 최대 주량 합이 T 이상이라면 S가 최소거나 더 작은 S가 존재한다는 뜻이다. 아니라면 S는 그 수보다 작다는 얘기다.
• S를 이진 탐색으로 찾아보자.

코드

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, T, S, Lsum, Rsum, Lmax, Rmax;
	static int[] L, R;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		T = Integer.parseInt(tk.nextToken());
		
		L = new int[N];
		R = new int[N];
		for (int i=0; i<N; i++) {
			tk = new StringTokenizer(rd.readLine());
			L[i] = Integer.parseInt(tk.nextToken());
			R[i] = Integer.parseInt(tk.nextToken());
			Lsum += L[i];
			Rsum += R[i];
			Lmax = Math.max(Lmax, L[i]);
			Rmax = Math.max(Rmax, R[i]);
		}
		
		if (T < Lsum || T > Rsum) {	// 모두 L만큼 먹어도 부족하거나 모두 R만큼 먹어도 남으면 안됨
			System.out.println(-1);
			return;
		}
		
		// S: Lmax~Rmax 이분탐색
		int lo = Lmax;
		int hi = Rmax;
		int S = -1;
		int sum;
		while (lo <= hi) {
			sum = 0;
			S = (lo + hi) / 2;
			for (int i=0; i<N; i++) {
				sum += Math.min(R[i], S);
			}
			if (sum >= T) hi = S - 1;
			else lo = S + 1;
		}
		
		System.out.println(S);
	}
}

메모리 및 시간

• 메모리: 14588 KB
• 시간: 148 ms

리뷰

• 이 문제가 이진 탐색 문제였다는 사실을 몰랐어도 풀 수 있었을까?