[BOJ/JAVA] 15810번: 풍선 공장

15810번: 풍선 공장

https://www.acmicpc.net/problem/15810

키워드

풍선을 담당하는 N명의 스태프

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

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

---

구현

매개변수 탐색을 이용하여 구현한다.

범위가 int 범위를 초과하므로 long 자료형을 이용한다.

템플릿

low, high 값은 항상 범위 내로 설정한다.

low = 1

high = 가장 빨리 만들 수 있는 직원이 걸리는 시간 * M

반복문의 속행 조건은 low≤high 이다.

long mid = (low + high) / 2;

mid 시간내로 만들 수 있는지 체크한다.

1. mid 시간 내로 만들 수 있다면
   • high = mid - 1 값으로 갱신한다.

2. mid 시간 내로 만들 수 없다면
   • low = mid + 1 값으로 갱신한다.

반복문 종료 시 low를 반환한다.

static long canMake()

mid 시간 내로 만들 수 있는지 체크하는 메소드

배열을 돌면서 M개의 풍선을 만들 수 있는지 체크한다.

i번째 직원이 mid시간에 만들 수 있는 풍선의 개수 = A_i/mid

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class java_15810 {
    // N : 스태프의 수
    // M : 풍선의 개수
    static int N, M;

    static List<Integer> staffList;

    // time 내로 목표 풍선을 제작할 수 있는가?
    static boolean canMake(long time) {
        long balloonCount = 0;

        for (int staff : staffList) {
            balloonCount += time / staff;
        }

        return balloonCount >= M;
    }

    static long binarySearch() {

        long low = 1;
        long high = (long)staffList.get(0) * M;

        while (low <= high) {
            long mid = (low + high) / 2;

            // mid 시간에 만들 수 있는가?
            boolean result = canMake(mid);

            if (result) {
                high = mid - 1;
                continue;
            }

            // 만들 수 없다면 -> 시간을 늘려보기
            low = mid + 1;
        }

        return low;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // M개를 만들기 위해 최소 시간
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        staffList = new ArrayList<>();

        // 데이터 삽입
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            staffList.add(Integer.parseInt(st.nextToken()));
        }

        // 오름차순 정렬
        Collections.sort(staffList);

        // M개의 풍선 만들기의 최소시간
        long result = binarySearch();

        System.out.println(result);

        br.close();
    }
}

---

Uploaded by N2T