2022.02.07 44일차

백준 15810번 (풍선 공장)

문제

전북대학교 프로그래밍 경진 대회에서는 ACM-ICPC 스타일을 따라 문제를 해결한 팀에게 그 문제에 해당하는 풍선을 달아준다.

풍선을 담당하는 N명의 스태프가 있다. 스태프마다 폐활량이 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간은 다양하다.

대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰가 들어왔다!

각 스태프가 풍선 하나를 만드는 시간(분) Ai를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?

풍선을 만든 후에 문제를 표시할 것이기 때문에 풍선의 종류는 상관이 없다.

모든 스태프는 풍선을 만드는 데에 정확하게 자신이 말한 시간만큼 걸린다. 예를 들어 스태프 A가 풍선 하나를 만드는 데 5분이 걸린다면, 0분에 만들기 시작해서 5분에 끝난다.

나의 풀이

1. 스태프 N, 풍선 M, 시간 nArr, 최소 시간(이분 탐색)
2. nArr에 해당하는 값이랑 중간값을 나눈 몫을 카운트(count)에 더하기
3. count >= M 이면 조건에 해당, 정답에 할당(Math.min으로 최소 비교), max 변경
4. 나머지 경우 조건 불충족, min 변경
5. 최소값(min): 배열 내 최소값으로 지정 , 최대값(max): 최소값에 풍선 개수 곱한 경우로 지정, 정답(answer): max로 지정(최소값 찾아야 함)
6. 경우의 수가 커지므로 long으로 계산

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

public class Main {
    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 M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] nArr = new int[N];
        long min = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            nArr[i] = Integer.parseInt(st.nextToken());
            min = Math.min(min, nArr[i]);
        }

        long max = min * M;
        long answer = max;

        while(min <= max) {
            long mid = (min + max) / 2;
            int count = 0;

            for (int x = 0; x < N; x++) {
                count += mid / nArr[x];
                if (count >= M) {
                    max = mid - 1;
                    answer = Math.min(answer, mid);
                }
            }
            if (count < M) {
                min = mid + 1;
            }
        }

        System.out.println(answer);
    }
}

생각하기

• 범위 생각하기
• 큐로도 접근 가능