백준 16801. 식신

n명의 먹는 사람들의 능력과 n개의 먹어야 할 음식들에 대한 값이 주어질 때, 점수는 능력 X 음식 의 값의 최댓값이 된다. 단련하여 1씩 능력을 줄여 0 까지 줄일 수 있고 k만큼 단련시킬 수 있을 때 점수의 최솟값을 구하는 문제이다.n <= 2* 10^5, k<= 10^18 이므로 모든 경우의 수를 세는 것이 아닌 최적의 경우의 수에서의 점수를 구해야 한다. 점수에 대한 이진탐색을 사용하여 최댓값을 구하였다.

 

이를 위해 능력과 음식들을 정렬한다.

players = new long[n];
st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++) players[i] = Long.parseLong(st.nextToken());
Arrays.sort(players);
            
foods = new long[n];
st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++) foods[i] = Long.parseLong(st.nextToken());
Arrays.sort(foods);

 

 

이진탐색은 점수에 대해 적용하였다. 정렬한 능력과 음식들을 서로 반대되는 위치의 값을 곱하는 것이 점수를 최대한 낮추는 최적의 방법이며 이진탐색의 점수를 최댓값으로 가지게 k를 사용할 때 가능한지 여부를 확인하면서 탐색하였다. 점수보다 큰 능력 X 음식값 을  기준으로 능력에 필요한 만큼만 빼줄 때 누적합이 k를 초과하게 되면 해당 점수 이하는 만들 수 없게 되며 시작점을 중앙+1로 이동한다. k 이하라면 해당 점수를 만들 수 있게 되어 종점을 중앙으로 이동한다. 종점이 시작점보다 작거나 같게 되면 구간의 종료가 되며 종점이 점수의 최솟값이 된다.

private static long binarySearch(long l, long r) {
    long start = l, end = r;
    while(end > start) {
        long mid = (start + end) / 2;
        long score = 0;
        for(int i=0; i<n; i++) {
            if(mid >= players[i] * foods[n -1 -i]) continue;
            score += players[i] - (mid / foods[n -1 -i]);
            if(score > k) {
                start = mid + 1;
                break;
            }
        }
        if(k >= score) {
            end = mid;
        }
    }
    return end;
}

 

 

결과 코드는 다음과 같다.

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

public class Solution {
    static long[] players;
    static long[] foods;
    static int n;
    static long k;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Long.parseLong(st.nextToken());
            
            players = new long[n];
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++) players[i] = Long.parseLong(st.nextToken());
            Arrays.sort(players);
            
            foods = new long[n];
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++) foods[i] = Long.parseLong(st.nextToken());
            Arrays.sort(foods);
            
            long answer = binarySearch(0, players[n-1] * foods[n-1]);
            sb.append(answer).append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
    
    private static long binarySearch(long l, long r) {
        long start = l, end = r;
        while(end > start) {
            long mid = (start + end) / 2;
            long score = 0;
            for(int i=0; i<n; i++) {
                if(mid >= players[i] * foods[n -1 -i]) continue;
                score += players[i] - (mid / foods[n -1 -i]);
                if(score > k) {
                    start = mid + 1;
                    break;
                }
            }
            if(k >= score) {
                end = mid;
            }
        }
        return end;
    }
}