[백준] 3079번 입국심사

3079 입국심사

문제

---

상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.

가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 

한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.

상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.

상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)

다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)

출력

---

첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다. 

---

풀이)

binary search 문제이다.

어렵지는 않은 문제였으나, 자료형을 잘못 지정한걸 늦게 알아서 헤맸던 문제이다.

사람수가 1,000,000,000 이고 심사대에서 걸릴 수 있는 시간이 1,000,000,000 이니깐 long long자료형을 사용해야했다.

또한 몇개는 int형 쓰고, 몇개는 long long을 쓰니깐 곱셈시에 overflow도 발생했다.

햇갈린다면 그냥 다 long long으로 두고 계산하는 것도 하나의 방법같다.

과정은 이러하다.

1. binary search로 상근이와 친구들이 입국심사하는 데 걸리는 시간을 예상한다.

2. 그 시간내에 각 심사대에서 몇명을 심사할 수 있는지 합을 구한다.

3. 만약 심사대에서 검사할 수 있는 인원이 상근이와 친구들을 넘어간다면, 시간을 줄이고

   인원이 부족하다면 시간을 늘린다.

위의 과정을 반복하면서 상근이와 친구들의 입국심사시 걸리는 시간의 최솟값을 구한다.

코드)

#include <stdio.h>
#include <vector>
#include<algorithm>
using namespace std;
 
int n, m;
long long time[100000];
 
int main() {
    scanf("%d %d", &n, &m);
    long long val = 0;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &time[i]);
        val = max(val, time[i]);
    }
    long long start = 1;
    long long end = val * m;
    long long result = val * m;
    while (start < end)
    {
        long long mid = (start + end) / 2; //시간
        //그 시간내에 몇명을 처리할수 있는지
        long long temp = 0;
        for (int i = 0; i < n; i++) {
            temp += mid / time[i];
        }
        //상근이와 친구들을 다 처리할 수 없을때
        if (temp < m) {
            start = mid + 1;
        }
        else {//처리할 수 있을때
            result = min(result, mid);
            end = mid;
        }
 
    }
    printf("%lld", result);
    return 0;
}

결과)