10주차(이진탐색) - [C++]백준3079 입국심사

23 May 2022 in Study on Algorithm

백준3079 입국심사 링크

문제

예제 입력

---

코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n, m;
vector<long long> arr; // long long안하면 틀림

long long Binary_Search() {
    long long st = 0;
    long long end = arr[n - 1] * m;
    long long res = arr[n - 1] * m;

    while (st <= end) {
        int temp = m;
        long long mid = (st + end) / 2;
        
        for (int i : arr) {
            temp -= (mid) / i;
        }
   
        if (temp <= 0) { // 사람이 남아서 시간 지점을 낮춰야함
            if (res > mid) res = mid;
            end = mid - 1;
        }
        else st = mid + 1; // 사람이 부족해서 시간 지점을 높여야함
    }
    return res;
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int time;
        cin >> time;
        arr.push_back(time);
    }
    sort(arr.begin(), arr.end());

    cout << Binary_Search();
}

설명

이 문제는 앞에서 했던 나무 자르기와 비슷한 유형으로 모든 사람이 최적의 시간 지점을 찾는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector를 사용하여 구현했습니다. 먼저 시간을 정렬하여 0~제일 긴 시간 사이에서 최적인 지점을 찾아야 하는데 적은 횟수로 하기위해서 중간 지점부터 확인하며 나무의 낭비가 최소가 되는 값에 점점 가까워지며 더이상 확인할 범위가 없으면 결과를 출력합니다.

<algorithm>
-sort(시작, 끝, 비교함수) : 배열의 크기만큼 정렬

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

---

결과