[백준] 15810번 풍선 공장 (JAVA)

문제

- N명의 스태프는 폐활량이 다 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간이 다양함

- 각 스태프가 풍선 하나를 만드는 시간 Ai를 알고 있을 때, 풍선 M개를 만들기 위해 필요한 최소의 시간은?

 

해결방법

풍선 하나를 만드는 데 가장 오래 걸리는 스태프가 M개를 다 만드는 것을 처음 시작으로 잡고 이분 탐색을 진행하였다. 해당 시간이 지났을 때, 몇개의 풍선을 불었는지 계산해보면서 이분 탐색을 진행하였다. 또, 자료형으로 틀렸다 !!!!! 자료형을 잘 생각하고 문제를 해결해야 할 것 같다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] staff = new int[N];
		
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++) {
            staff[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(staff);

	// 이분 탐색 시작
        // 풍선 하나를 부는 데 가장 오래 걸리는 스태프가 다 부는 것을 처음 기준으로 잡고 시작
        long left = 0;
        long right = (long)staff[0] * (long)M;
		
        // 이분 탐색
        while (left <= right) {
            long mid = (left + right) / 2;
            long count = 0;
			
            // 그 시간 내에 몇개의 풍선을 불 수 있는지 확인
            for(int i = 0; i<N; i++) {
                count += mid / (long)staff[i];
            }
			
            // 풍선의 개수에 따라 범위 재조정
            if(count >= M) right = mid - 1;
            else left = mid + 1;
        }

        System.out.println(left);
    }
}