반갑습니다!

[백준] 3079 입국심사 본문

알고리즘 문제 풀이

[백준] 3079 입국심사

김덜덜이 2020. 9. 11. 21:11
3079번: 입국심사
 
www.acmicpc.net

풀이

[프로그래머스] 입국심사와 동일한 문제이다.

코드

#include <iostream>
#include <algorithm>
#include <limits>
using namespace std;

int n, m;
int t[100001];

long long binary_search() {
    long long ans = numeric_limits<long long>::max();
    long long left = 1;
    long long right = (long long)(*max_element(t, t + n)) * (long long)m;

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

        long long cnt = 0;
        for (int i = 0; i < n; i++)
            cnt += mid / t[i];

        if (cnt < m) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
            ans = min(ans, mid);
        }
    }
    return ans;
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> t[i];
    cout << binary_search() << '\n';
    return 0;
}

'알고리즘 문제 풀이' 카테고리의 다른 글

[백준] 9656 돌 게임 2  (0) 2020.09.12
[백준] 6236 용돈 관리  (0) 2020.09.11
[백준] 2776 암기왕  (0) 2020.09.11
[백준] 2343 기타 레슨  (0) 2020.09.11
[백준] 12015 가장 긴 증가하는 부분 수열 2  (0) 2020.09.11