가능한 정답의 최소시간 = 1과 확실하게 가능한 정답중의 하나 = ((대기자의 수 / 심사관의 수) + 1 ) * 가장 느린 심사속도 두개를 시작점으로 해서 이분탐색을 돌리면 됩니다.
이분 탐색 문제는 언제나 탐색을 멈추는 조건을 정하는게 어려운데, 문제가 보통 정답의 최댓값이나 최솟값을 요구합니다. 우리는 문제에 따라 확실하게 가능한 정답과 확실하게 정답이 아닌 것+1을 줄여가다가 둘이 겹치는 곳에서 문제가 요구하는 답을 찾을 수 있습니다.
public class q43238_Programmers_입국심사 {
public static void main(String[] args) {
int n = 6;
int[] times = { 7, 10 };
System.out.println(solution(n, times));
}
private static long solution(int n, int[] times) {
long answer = 0;
long max = 0;
for (int t = 0; t < times.length; t++) {
max = Math.max(max, times[t]);
}
long left = 1;
long right = ((n / times.length) + 1) * max;
while (left < right) {
long center = (left + right) / 2;
long count = 0;
for (int t = 0; t < times.length; t++) {
count += (center / times[t]);
}
if(count >= n) {
right = center;
}else {
left = center + 1;
}
}
answer = right;
return answer;
}
}
핵심아이디어는 돈이 허락하는 범위 안에서 5000원짜리 메뉴를 먹었을때 얻는 상대적 만족도가 가장 큰 경우를 선택해야 한다는 것입니다.
예를 들어서, 극단적으로 5000원짜리 메뉴의 만족도가 1만이라고 해도 1000원짜리 메뉴의 만족도가 9999라면 상대적 만족도는 1에 불과합니다. 또 역으로 1000원짜리 메뉴가 더 만족스러운 경우도 가능할 수 있습니다.
가장 만족스러운 식사를 하려면 날짜와 만족도에 상관없이 상대적 만족도가 큰 5000원짜리 메뉴부터 골라서 가능한만큼 선택하는것이 해결방법입니다.
따라서 A메뉴와 B메뉴의 만족도의 차이를 기준으로 입력된 데이터를 정렬해주고, 돈이 허락하는 한에서 A메뉴를 선택했습니다. 돈이 가능한지 여부는 (골라야하는 남은 메뉴의 갯수 * 1000) + 4000 보다 현재 자금이 크거나 같으면 가능하다고 조건문을 잡아두었고 메뉴를 하나 고를때 마다 자금에서 5000원씩을 빼 주었습니다.
또, 정렬을 통해서 B메뉴의 만족도가 더 큰 시점이 오면 이후로는 전부 B메뉴를 선택했습니다. B메뉴를 선택하기 시작한 경우는 두가지입니다.
1. 돈이 부족해서 남은 모든 식사는 B메뉴로 골라야 한다. (조건문을 통해 보장됨)
2. 남은 모든 식사들은 B메뉴가 A메뉴보다 맛있다. (정렬을 통해 보장됨)
따라서 이후로는 돈 계산을 하지 않고 B메뉴의 만족도를 계속 더해주었습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static StringTokenizer st;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long answer = 0;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int money = Integer.parseInt(st.nextToken());
int[][] menu = new int[N][2];
for (int n = 0; n < N; n++) {
st = new StringTokenizer(br.readLine());
menu[n][0] = Integer.parseInt(st.nextToken());
menu[n][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(menu, (e1, e2) -> {
return (e2[0] - e2[1]) - (e1[0] - e1[1]);
});
int n = 0;
while (money - ((N - n) * 1000) >= 4000) {
if(menu[n][1] > menu[n][0]) {
break;
}
answer += menu[n][0];
money -= 5000;
n++;
}
while (n < N) {
answer += menu[n][1];
n++;
}
System.out.println(answer);
}
}
