[BOJ] 1561번: 놀이공원

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

1561번: 놀이 공원

---

접근 방법

처음엔,

문제에서 구하라는 것을 직접적으로 n번째 아이가 몇 번째 놀이기구를 타게 될 지를 고민했었다.

필연적인 사고였지만, 직접 손으로 시행을 해보면서 얻은 결과는 모든 운행 시간들의 배수마다 매번 몇 명의 아이들이 타는 지, 총 몇 명의 아이들이 탔는지를 생각해주어야 하는데,

이는

1. n번째 아이가 탈 때가 언제인지 미리 알 수 없다는 점,

2. 모든 운행 시간들의 배수만 확인하는게 쉽지 않다는 점

때문에 다른 방법을 생각해보기로 했다.

 

그 다음엔,

시간을 기준으로 생각을 해 보았다.

어느 정도의 시간이 있어야 n번째 아이도 놀이기구를 탈 수 있을까? 라는 생각을 했고,

여기서 총 시간을 기준으로 이분 탐색을 하면 풀 수 있지 않을까? 라는 생각으로 풀었다.

---

풀이 

총 시간을 기준으로 이분 탐색을 하자.

\(총 시간 동안 탈수 있는 놀이 기구의 횟수 = cnt\)  라 하자.

\(cnt \geq n\) 일때에는 총 시간을 작게

\(cnt<n\) 일때에는 총 시간을 크게 하는 이분 탐색을 하자.

이때,\( cnt=((총 시간)/a[i])+1 (1 \leq i \leq m)\) 이다.

이러면 최종적으로 이분 탐색의 결과로서 ans에는 n명의 아이들이 모두 놀이기구를 탈 수 있는 시간의 최솟값이 저장된다.

 

이제 n번째 아이가 탈 놀이기구의 번호를 구해보자.

\(ans%a[i]==0\) 는 ans분째에 i번 놀이기구를 탈 수 있다는 뜻이므로, 이런 i를 nums 배열에 저장해두자.

\(cnt == (ans-1)분까지 탄 놀이기구의 수\) 라 하면

\(n-cnt\)는 ans분째 탈 놀이기구의 수가 되므로

정답은 nums[(n-cnt)-1] 이다.

---

시간 복잡도

\(O(m*lg(r-l))\) 

l의 가능한 최소는 1

r가 가능한 최대는 \(30*20억=600억=6*1e11\) 

이므로 최악의 경우에 대략 \(10000*39\)번의 연산을 하므로 충분히 시간 안에 가능하다.

---

코드

#include <bits/stdc++.h>
#define ll long long int
#define pll pair<ll, ll>
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;
int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};
void solve()
{
    ll n, m; cin>>n>>m;
    ll a[m+1], l=0, r=n, mx=1, ans;
    for(int i=1;i<=m;i++)
    {   
        cin>>a[i];
        if(a[i]>mx) mx=a[i];
    }
    r*=mx;
    if(n<=m) //0분만에 마지막 아이가 놀이기구를 타는 경우 처리
    {
        cout<<n<<'\n';
        return ;
    }
    while(l<=r)
    {
        ll mid=(l+r)/2;
        ll cnt=m; //0분에 탄 학생 뒤에서 포함 안되므로 여기서 처리
        for(int i=1;i<=m;i++) cnt+=(mid/a[i]);
        if(cnt>=n)
        {
            r=mid-1;
            ans=mid; //최종적으로 ans에는 n명의 아이들이 모두 놀이기구를 탈 수 있는 시간의 최솟값이 저장된다.
        }
        else l=mid+1;
    }

    vector<int> nums;
    ll cnt=m;
    for(int i=1;i<=m;i++)
    {
        cnt+=ans/a[i];
        if(ans%a[i]==0) 
        {
            cnt--;
            nums.push_back(i); //ans분째에 탈 수 있는 놀이기구의 번호 저장
        }
    }
    cout<<nums[(n-cnt)-1]<<'\n'; //cnt에는 (ans-1)분째까지 아이들이 탄 놀이기구 수, 결국 n-cnt는 ans분째 탈 놀이기구 수
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int tc=1;
    while(tc--) solve();
    return 0;
}