[백준] 24041번 : 성싶당 밀키트[Java]

#풀이

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N;
        long G,K;
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        G = Long.parseLong(st.nextToken());
        K = Long.parseLong(st.nextToken());
        long[][] ingredient = new long[N][4];
        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            ingredient[i][0] = Long.parseLong(st.nextToken());
            ingredient[i][1] = Long.parseLong(st.nextToken());
            ingredient[i][2] = Long.parseLong(st.nextToken());
        }
        long left = 1L;
        long right = Integer.MAX_VALUE-1;
        long ans = -1;
        long answer = -1;
        while(left<=right){
            ans = (left+right)/2;
            //각 재료별 세균 구하기
            for(int i = 0; i<N; i++){
                ingredient[i][3] = ingredient[i][0]*Math.max(1,ans-ingredient[i][1]);
            }
            //정렬하기 (세균수 기준 오름차순)
            Arrays.sort(ingredient,(a,b)->{
                return Long.compare(b[3],a[3]);
            });
            //재료빼기
            int minus = 0;
            for(int i = 0; i<N; i++){
                if(ingredient[i][2]==1&&minus<K){
                    minus++;
                    ingredient[i][3] = 0;
                }
                if(minus>=K)break;
            }
            // 전체 세균 합 구하고 G랑 비교하기
            long sum = 0;
            for(int i = 0; i<N; i++){
                sum+=ingredient[i][3];
                if (sum > G) break;
            }
            if(sum<=G){
                answer = ans;
                left = ans+1;
            }
            else right = ans-1;

        }

        System.out.println(answer);

    }
}

#성능

#정리

1. 재료 수 N, 허용 세균량 G, 제거 가능 개수 K를 입력받는다.

2. 이분 탐색으로 가능한 최대 일수 mid를 찾는다.

3. 각 재료별로 (mid – 유통기한) 이상인 일수만큼 곱해 세균 수를 계산하고, 내림차순으로 정렬한다.

4. 중요 표시된 재료 중 상위 K개만 세균 수를 0으로 처리해 제거한다.

5. 남은 재료들의 세균 합이 G 이하면 mid를 갱신하고 범위를 늘리고, 초과하면 범위를 줄인다.

6. 탐색이 완료되면 최종 mid 값을 출력한다.