[백준(BOJ)] 3079번 : 입국심사 - C++[CPP]

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

3079번: 입국심사

 

---

 

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 이분 탐색

 

---

 

⊙ 문제 접근 과정

 

그냥 문제에 접근해 풀이한다면 대부분 아마 시간 초과를 피할 수 없을 거다.

아래 코드처럼 이진 탐색 알고리즘으로 문제를 풀면 시간 초과 문제를 해결할 수 있다.

---

 

⊙ 문제 풀이

 

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

using namespace std;
typedef long long ll;

ll n,m;
vector<ll> people;

int main() {
    cin>> n >> m;

    for (auto i = 0;i<n;i++) {
        int x;
        cin>> x;
        people.push_back(x);
    }
    sort(people.begin(),people.end());

    ll start=1;
    ll end = *max_element(people.begin(),people.end())*m;
    ll result=end;

    while(start <= end) {
        ll mid = (start + end) /2;

        ll sum =0;
        for(int i=0;i<n;i++) {
            sum+=mid/people[i];
        }

        if(sum<m)
            start=mid+1;
        else {
            result=mid;
            end=mid-1;
        }
    }

    cout << result;
}

---

⊙ 결과

 

---

 

 

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!