[백준] 3079번 입국심사 (C++)

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

 

 

이 문제는 N개의 입국심사대와 M명의 인원이 주어질때 각 입구심사에서 심사를 보는 시간이 주어진다.

 

M명이 입국심사를 다 했을때 최소시간을 출력해야한다.

 

첫번째 테스트케이스를 계산해보니 어떤 알고리즘을 사용해서 구해야하는지 깨달았다.

 

 

먼저 시간을 이분탐색으로 구해야하는데 이때 정답 분포 범위는 FFFFFTTTTT로 앞쪽의 시간이 답의 분포가 적고 뒤쪽이 될 수 있는 확률이 크다 따라서 lo + 1 < hi 으로 범위를 설정하여 각 입국심사대마다 나올 수 있는 인원을 구하여 M과 비교해주었다.

 

이때 M보다 큰 경우 이는 시간을 더 높여야 하므로 left = mid로 설정하고 아닌 경우 더 낮춰야 하므로 right = mid로 설정하여 답을 해결하였다.

 

이때 입국심사대의 시간대는 10^9이므로 입국심사대가 10만개이므로 right값을 넉넉하게 10^18으로 잡았다.

 

하지만 여기서도 계속 틀렸습니다를 받아서 왜 그럴까 계속 디버깅하여 살펴보니 인원수를 구할때도 시간대가 작은 경우 수가 커지기 때문에 루프를 돌며 일찍히 M보다 큰 경우 바로 리턴을 하였다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e18

struct coordinate {
    int x;
    int y;
    int r;
};

struct halloween {
    int cnt;
    int score;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
// int dx[] = {0, 0, 1, -1};
// int dy[] = {1, -1, 0, 0};
int dx[] = {1, 0};
int dy[] = {0, 1};
int graph[1002][1002];
int N, M;
int arr[100001];

bool check(ll time) {

    ll people = 0;
    for(int i = 0; i < N; i++) {
        people += (time / arr[i]);
        if(people >= M) return people >= M;
    }

    return people >= M;
}

void solve() {
    ll left = 0;
    ll right = MAX;

    while(left + 1 < right) {
        ll mid = (left + right) / 2;

        if(check(mid)) {
            right = mid;
        }
        else left = mid;
    }

    cout << right;
}

void input() {
    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        cin >> arr[i];
    }
}

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

    input();
    solve();
}