문제
도현이는 이번 대회를 준비하면서 거한 저녁 만찬을 예약했다.
하지만 모종의 이유로 요리사들이 모두 천국으로 떠나버렸기 때문에, 도현이는 어쩔 수 없이 평범한 신촌 술집을 뒤풀이 장소로 정할 수밖에 없었다.
도현이는 우선 각 사람에게 어느 정도 마시면 기분이 좋은지()와, 어느 정도 마시면 힘든지()를 물어보았다. 각 사람은 Li미만의 술을 마시면 술이 부족해 기분이 좋지 않고, Ri를 초과하는 술을 마시면 천국으로 가버릴 수도 있다. 도현이는 각 사람들에게 적당량씩 술을 분배하려고 한다.
그런데 신촌 술집이 항상 그렇듯이, 사장님은 도현이에게 T이상의 술을 반드시 팔아줘야만 예약을 잡아주겠다고 엄포를 놓았다. 마침 도현이의 통장엔 정확히 T의 술을 살 수 있는 금액이 들어 있었고, 도현이는 정확히 T의 술을 결제하였다.
이제 도현이는 모든 사람 i에게 이상 이하의 술을 주면서, 그 총합이 정확히 T가 되도록 술을 분배하려고 한다. 하지만 안타깝게도, 사람들은 자신의 주량을 과대평가하는 경향이 있다. 이에 따라 도현이는 S의 값을 정하고, 각 사람에게 그 사람이 원하는 술의 양이 얼마이던지 관계없이 S이하의 술만을 주려고 한다. 이제 도현이는 술도 결제했고, 주량도 조사했으므로,
- 모든 사람 i가 이상 이하의 술을 받으면서,
- 모든 사람이 받은 술의 총합이 정확히 T가 되고,
- 어떤 사람도 S를 초과하는 술은 받지 않게 할 수 있는,
그러한 S값만 결정하면 된다.
도현이를 도와 조건을 만족하는 S값을 찾아주도록 하자.
만약 그런 값이 여러 개라면, 도현이는 그 중 가장 작은 값을 찾고 싶다.
입력
첫째 줄에 대회 참가자의 수 N과 술의 총량 T가 주어진다. (1 ≤ N ≤ 1000, 1 ≤ T ≤ 109)
둘째 줄부터 N개의 줄에 걸쳐, 각 사람에 대한 와 값이 주어진다. (1 ≤ ≤ ≤ 106)
출력
만약 S의 값과는 관계없이 항상 불가능하다면 첫째 줄에 -1만을 출력한다.
문제의 조건을 만족하는 S값이 존재한다면 가장 작은 값 하나를 출력한다.
예제 입력 1
3 10
2 5
4 10
1 3예제 출력 1
4문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ14575 {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
int N=Integer.parseInt(st.nextToken());
int T=Integer.parseInt(st.nextToken());
int[][] drink=new int[N][2];
int lsum=0;
int rsum=0;
for(int i=0;i<N;i++){
st=new StringTokenizer(br.readLine());
int a=Integer.parseInt(st.nextToken());
int b=Integer.parseInt(st.nextToken());
drink[i][0]=a;
drink[i][1]=b;
lsum+=drink[i][0];
rsum+=drink[i][1];
}
int left=0;
int right=T;
if(lsum>T || rsum<T){
System.out.println(-1);
System.exit(0);
}
while(left<=right){
// S값
int mid=(left+right)/2;
int sum=0;
boolean flag=false;
for(int i=0;i<N;i++){
if(drink[i][0]>mid){
flag=true;
break;
}
sum+=Math.min(drink[i][1],mid);
}
if(flag){
left=mid+1;
continue;
}
if(sum>=T){
right=mid-1;
}
else{
left=mid+1;
}
}
System.out.println(left);
}
}이분탐색을 이용하여 모든 사람이 마신 술의 양이 T를 넘기는 지에 따라 S 값을 구하는 문제다.
이때, 마신 술의 양이 T와 같아야 하므로 T가 되지 않는 경우가 발생 할 수 있으므로 탐색 전에 T를 만들 수 있는지 먼저 확인해준다.
T를 만족할 수 없는 경우
int lsum=0;
int rsum=0;
for(int i=0;i<N;i++){
st=new StringTokenizer(br.readLine());
int a=Integer.parseInt(st.nextToken());
int b=Integer.parseInt(st.nextToken());
drink[i][0]=a;
drink[i][1]=b;
lsum+=drink[i][0];
rsum+=drink[i][1];
}
int left=0;
int right=T;
if(lsum>T || rsum<T){
System.out.println(-1);
System.exit(0);
}각 사람들의 L값과 R값을 각각 모두 더한 값을 lsum, rsum에 저장해둔다.
그리고 lsum 값이 T를 넘기게 되면 가장 작은 값들을 합쳐도 T를 넘어간다는 뜻이므로 T를 만족할 수 없게 된다.
또한 rsum 값이 T보다 작은 경우에도 제일 큰 값들을 합쳐도 T보다 작다는 뜻이므로 T를 만족할 수 없으므로 이 경우들은 애초에 T를 만족할 수 없다.
때문에 -1을 출력하고 프로그램을 종료한다.
이분탐색
while(left<=right){
// S값
int mid=(left+right)/2;
int sum=0;
boolean flag=false;
for(int i=0;i<N;i++){
if(drink[i][0]>mid){
flag=true;
break;
}
sum+=Math.min(drink[i][1],mid);
}
if(flag){
left=mid+1;
continue;
}
if(sum>=T){
right=mid-1;
}
else{
left=mid+1;
}
}
System.out.println(left);T를 만족할 수 있는 조건이라면 이분탐색을 진행한다.
mid는 구해야하는 S의 값이라고 생각하면 된다.
마실 수 있는 술의 한계점(mid)를 정한 뒤, 사람들이 마실 수 있는 술의 양을 정한다.
이때, 우리는 S의 최소값을 구해야하는데 그러기 위해서는 각 사람들의 R만큼 술을 마시면 된다.
예를 들어 한 사람이 최소 3잔, 최대 7잔을 마실 수 있다고 했을 때 최소 잔수를 기준으로 값을 모두 더하게 되면 T보다 작아지는 경우가 많아지기 때문에 S의 최소값이 아니라 최대값을 구하게 되버린다.
때문에 S의 최소값을 구하기 위해서는 사람들의 최대 잔 수를 더하여 정답을 구한다.
하지만 S값을 넘기면 안되기 때문에
sum+=Math.min(drink[i][1],mid);R값과 mid값 중 작은 값을 더한다.
그리고 mid값이 L값보다 작다면 조건에 부합하지 않기 때문에 mid값을 키워줘야한다.
flag를 이용하여 mid값을 조정해준다.
if(drink[i][0]>mid){
flag=true;
break;
}
...
if(flag){
left=mid+1;
continue;
}합을 구하고 나면 sum값이 T를 넘기는지 확인한다.
T랑 같거나 크면 S의 최솟값을 구하기 위해 마실 수 있는 술을 줄여 S값을 줄여본다.
반대로 T보다 작다면 술을 더 마실 수 있으므로 S값을 키워본다.
if(sum>=T){
right=mid-1;
}
else{
left=mid+1;
}이 과정을 모두 거치고 나면 답을 구할 수 있다.
