[C++] 백준/BOJ - 3079 : 입국심사

문제 이해 단계

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

3079번: 입국심사

N개의 심사대와 M명이 주어진다.
각 심사대마다 심사하는데 소요되는 시간이 존재한다.

M명은 한 줄로 서서 자기 차례를 기다리는데,
여러 개의 심사대 중 하나를 골라서 갈 수 있다.

이미 심사가 진행 중인 곳은 가지 못한다.
또한 몇 초를 기다렸다가 가는 것도 가능하다.

여러 가지 수를 조합해서 M명이
최대한 빨리 심사를 마치는 경우의 수를 조합할 때, 이때의 최소 소요 시간이 얼마인지 구하는 문제이다.

 

---

문제 접근 단계

늘 그랬듯, 문제의 제한사항부터 살펴보자.

심사대 N은 최대 100,000개, 사람 M은 최대 10^9, 시간의 최댓값도 10^9이다.

자칫하면 오버플로우가 나기 쉬울 것 같아서
int 보다 큰 자료형을 사용하는 것이 나을 것 같다.

해당 문제를 처음 풀 때는 시간이 최소화되도록 M명을 배분하는 것에 집중했다.
그렇게 해도 딱히 좋은 수가 나오지 않아서 관점을 바꿔 시간에 집중해 보기로 했다.

시간이 10초이고, 심사대가 3초짜리, 4초짜리, 5초짜리가 있다고 가정해 보자.

각 심사대는 10초 동안 최대 몇 명까지 처리할 수 있을까?

3초 - 3명
4초 - 2명
5초 - 2명

이렇게가 최댓값일 것이다.

이걸 다르게 말해보면,
10초 동안 최대 3+2+2 = 7명까지 처리할 수 있다는 소리이다.
이걸 이용해서 해당 문제를 풀 수 있다.

문제에서 주어진 M을 목표로 시간 T를 계속 예측해 보는 것이다.

근데 시간 T는 1초 ~ 10^9초까지 존재한다.
이걸 하나하나 다 탐색할 순 없다.

그래서 이를 이분탐색을 이용해서 탐색한다.

시간 T의 최댓값은 M명이 모두 시간이 가장 오래 걸리는 심사대로 갔을 때의 시간으로 한다.
이분탐색에 대한 것은 코드로 설명하는 것이 더 빠르다.

 

---

문제 구현 단계

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    unsigned long long N,M;
    cin >> N >> M;
    vector<unsigned long long> v(N); // 심사대
    for(int i = 0; i < N; i++) cin >> v[i];

    sort(v.begin(),v.end()); // 시간이 적게 걸리는 순으로 정렬

    // 최대값을 전원이 시간이 가장 오래걸리는 심사대로 갔을 때로 가정
    unsigned long long high = M * v[v.size()-1]; 
    unsigned long long low = 1;

    unsigned long long mid;
    unsigned long long ans = 0;

    // 이분탐색
    while(high >= low){
        mid = (high+low) / 2; // 절반으로 끊어서 mid

        unsigned long long sum = 0; // 가능한 최대 인원수
        for(int i = 0; i < v.size(); i++) sum += (mid/v[i]);
        if(sum >= M) { // M 이상일 때만 ans에 최솟값 담아줌(성공으로 간주)
            high = mid - 1;
            if(ans > mid || ans == 0) ans = mid;
        }
        else low = mid + 1;
    }
    cout << ans;
}

이분탐색을 진행하는 코드 전체이다.

자료형을 unsigned long long으로 한 이유는,
최대한 큰 양의 정수형을 받기 위해서이다.

입력으로 받은 심사대를 오름차순으로 정렬한 후, 이분탐색을 시작한다.

이분탐색은 정렬이 되어있는 경우만 할 수 있는데,
애초에 시간은 오름차순이기 때문에 가능하다.

이분탐색에서 중요한 것은
(시간/심사대) = 심사대에서 심사할 수 있는 사람의 수
이기 때문에 이를 모두 더해줘 최대 인원수를 구해준다.

그리고 이 인원이 M 이상이어야지
M명을 다 심사한 것이기 때문에 성공으로 간주한다.

 

---

시행착오

솔직히 이분탐색인 줄 몰랐다. 처음에는 우선순위큐로 풀었다.
그리고 우선순위큐로 푸는 게 당연한 줄 알았다.

로직도 완벽하고 거의 다 풀었다고 생각했다.
그런데 계속 틀렸다고 해서, 멘탈 나가고..

질문 게시판에 있는 케이스 돌려보니까 확실히 틀리긴 했는데,
그럼 어떻게 해야 할지 모르겠어서 그냥 답지 보니까 이분탐색이란다.

이분탐색을 여기서 떠올리신 분들은 대단한 것 같다.
나도 저렇게 좀 잘 풀고 싶다.

 

https://toss.me/howudong

토스아이디