[백준14575] 뒤풀이 / Java

링크 | https://www.acmicpc.net/problem/14575

문제 |

도현이는 이번 대회를 준비하면서 거한 저녁 만찬을 예약했다.

하지만 모종의 이유로 요리사들이 모두 천국으로 떠나버렸기 때문에, 도현이는 어쩔 수 없이 평범한 신촌 술집을 뒤풀이 장소로 정할 수밖에 없었다.

도현이는 우선 각 사람에게 어느 정도 마시면 기분이 좋은지(Li)와, 어느 정도 마시면 힘든지(Ri)를 물어보았다. 각 사람은 Li미만의 술을 마시면 술이 부족해 기분이 좋지 않고, Ri를 초과하는 술을 마시면 천국으로 가버릴 수도 있다. 도현이는 각 사람들에게 적당량씩 술을 분배하려고 한다.

그런데 신촌 술집이 항상 그렇듯이, 사장님은 도현이에게 T이상의 술을 반드시 팔아줘야만 예약을 잡아주겠다고 엄포를 놓았다. 마침 도현이의 통장엔 정확히 T의 술을 살 수 있는 금액이 들어 있었고, 도현이는 정확히 T의 술을 결제하였다.

이제 도현이는 모든 사람 i에게 Li이상 Ri이하의 술을 주면서, 그 총합이 정확히 T가 되도록 술을 분배하려고 한다. 하지만 안타깝게도, 사람들은 자신의 주량을 과대평가하는 경향이 있다. 이에 따라 도현이는 S의 값을 정하고, 각 사람에게 그 사람이 원하는 술의 양이 얼마이던지 관계없이 S이하의 술만을 주려고 한다. 이제 도현이는 술도 결제했고, 주량도 조사했으므로,

모든 사람 i가 Li이상 Ri이하의 술을 받으면서,
모든 사람이 받은 술의 총합이 정확히 T가 되고,
어떤 사람도 S를 초과하는 술은 받지 않게 할 수 있는,
그러한 S값만 결정하면 된다.

도현이를 도와 조건을 만족하는 S값을 찾아주도록 하자.

만약 그런 값이 여러 개라면, 도현이는 그 중 가장 작은 값을 찾고 싶다.

입력 |

첫째 줄에 대회 참가자의 수 N과 술의 총량 T가 주어진다. (1 ≤ N ≤ 1000, 1 ≤ T ≤ 109)

둘째 줄부터 N개의 줄에 걸쳐, 각 사람에 대한 Li와 Ri값이 주어진다. (1 ≤ Li ≤ Ri ≤ 106)

출력 |

만약 S의 값과는 관계없이 항상 불가능하다면 첫째 줄에 -1만을 출력한다.

문제의 조건을 만족하는 S값이 존재한다면 가장 작은 값 하나를 출력한다.

예제 |

입력

3 10
2 5
4 10
1 3

출력

4

Solution |

• 이분탐색 사용

• 최소값의 합보다 작고 최대값 합보다 작은 경우 S값과 관계없이 불가능하므로 -1 출력

• mid값이 최소값보다 작다면 해당 S값은 불가능하므로 return Search_S(high, mid+1)

• mid와 최대값 중 더 작은 값의 합 sum을 구하여 sum이 술 총량 T보다 크면 Search_S(mid-1, low) 작으면 Search_S(high, mid+1)

• sum이 T값과 같거나 S가 가능한 최소값이 였다면 low>high가 되므로 이때의 low값 return.

cf) sum>=T인 경우 high=mid-1로 설정한다면 재귀함수를 끝내는 조건을 low>high return low로 해주어야한다.(low>=high로 조건문을 설정하면 오류) high=mid로 한다면 low>=high return low or return high로 조건문을 설정 해야한다.
속도는 mid-1로 설정한 경우가 경우의 수를 더 빠르게 줄어주어 더 빠름.

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

public class AfterParty {
	static int T, N;
	static int[][] drink;
	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()); // 참가자 수 
		T  = Integer.parseInt(st.nextToken()); // 술 총합
		
		drink = new int[N][2];
		int high_sum=0, low_sum=0;
		for(int i = 0; i<N; i++) {
			st = new StringTokenizer(br.readLine());	
			drink[i][0] = Integer.parseInt(st.nextToken());
			drink[i][1] = Integer.parseInt(st.nextToken());
			
			low_sum += drink[i][0];
			high_sum += drink[i][1];
		}
		
		if(low_sum > T || high_sum < T) {
			System.out.println(-1);
			System.exit(0);
		}
		
		System.out.println(Search_S(T, 0));
	}
	
	static int Search_S(int high, int low) {
		int mid = (high+low)/2;
		if(low > high) {
			return low;
		}
		
		int sum=0;
		for (int i=0; i<N; i++) {
			if (drink[i][0] > mid) {
				return Search_S(high, mid+1);
			}
			sum += Math.min(drink[i][1],mid);
		}
		
		if (sum >= T) {
			return Search_S(mid-1, low);
		}else{
			return Search_S(high, mid+1);
		}
	}
}