백준 1561 : 놀이 공원

문제 링크

이분 탐색을 통해 해결하였다.

시간이 늘어남에 따라 태울수 있는 사람이 증가함수의 꼴로 늘어나므로, 시간이 x일 때 n명 이상을 태울 수 있는가?를 결정함수로 하여 이분 탐색을 적용하는데 문제가 없다. 따라서 n명이상을 태울 수 있는 최소의 시간을 찾아 준 후, 그 시간 -1까지 사람들을 태운 다음 그 다음 시간대에서 한 명씩 태우면서 n명이 될때의 놀이기구의 번호를 출력하면 된다. n <= 2*1e9이고 한번 타는데 최대 30분이 소요되므로, int 범위를 벗어나는것을 주의해야 한다.

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const ll INF = 1LL<<60;
const int MAX = 1e9;

vector<int> vec;
vector<int> cnt;
ll n,m;

bool can(ll x)
{
    ll temp = 0;

    for(int i = 1;i<=30;i++)
    {
        temp += 1LL * cnt[i] * (x/i + 1);

        if(temp >= n) return true;
    }

    return false;
}

ll bisearch(ll s,ll e)
{
    if(s >= e) return e;

    ll x = (s+e)/2;

    if(can(x)) return bisearch(s,x);
    else return bisearch(x+1,e);
}

int main()
{
    ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
 
 
    cin>>n>>m;

    vec = vector<int>(m);
    cnt = vector<int>(31,0);

    for(int i = 0;i<m;i++)
    {
        cin>>vec[i];
        cnt[vec[i]]++;
    }

    ll lim = bisearch(0,INF);
    ll temp = 0;

    if(lim != 0)
    {
        lim--;

        for(int i = 1;i<=30;i++)
        {
            temp += cnt[i] * (lim/i + 1);
        }

        lim++;
    }
    
    for(int i = 0;i<m;i++)
    {
        if(lim % vec[i] == 0)
        {
            temp++;

            if(temp == n)
            {
                cout<<i+1;
                break;
            }
        }
    }
    return 0;
}
​