3079 입국심사

이분탐색 특징을 알겠다. 문제 이해는 잘 되는데 풀기가 어려움.

이 문제를 두시간 동안 잡고 있었다 하면 믿으시겠습니까!

 

 

 

고민고민하다 갑자기 방법이 생각났다. 초를 범위로 잡고 그 범위에서 통과할 수 있는 명 수를 구한다. mid초 안에 m명보다 많이 통과할 수 있다면 True! 못하면 False! 

 

예를 들어 초가 5초라면 2초인 심사는 두 명 통과시킬 수 있고 3초인 심사는 1명, 4초인 심사는 1명을 통과시킬 수 있다. 그러므로 5초 안에 총 4명이 지나갈 수 있다. 이런 식으로 초가 주어졌을 때 지나갈 수 있는 최대 사람 수를 구하고 m명보다 큰지 작은지 확인한다. 

 

 

 

처음 코드는 이렇게 짰다. 이 때까지 풀었던 문제랑 다른 점이라면, 전에는 low = 만족하는 범위 high = 불만족하는 범위로 잡았는데 지금은 반대다. high가 만족이고 low가 만족하지 않는 범위이다. 그래서 low는 1*M - 1으로 두고 high는 max*N으로 뒀다. (<- 코드 짜면서 수정함) low가 1*M - 1인 이유는 Tk의 최솟값이 1이라 (1 ≤ Tk ≤ 109) 만족하지 않으려면 1*M보다작아야 한다고 생각해서이다. 아 그리고 while문 빠져나오는 조건도 범위가 (low, high]라 (low + 1 == high)로 잡았다. 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

bool check(i64 mid, int m, vector<i64> v){
    i64 count = 0;
    for(int i = 0; i < v.size(); i++){
        count += mid / v[i];
    }
    if(count >= m)
        return true;
    return false;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<i64> v(n);
    
    for(int i = 0; i < n; i++)
        scanf("%lld", &v[i]);
    
    i64 low = 0;
    i64 high = *max_element(v.begin(), v.end())*m;
    
    while(true){
        if(low + 1 == high)
            break;
        i64 mid = (low + high)/2;
        if(check(mid, m, v))
            high = mid;
        else
            low = mid;
    }
    
    printf("%lld", high);
    
}

그런데 코드가 계속 안 돌아가길래 이유를 찾다가 low를 0으로 잡으니 해결됐다. (틀왜맞) 원인은 모르겠다. 그저 맞았다는 거에 감사한다.