[BOJ] 놀이 공원 1561번 C++

 

문제

N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.

모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.

놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.

출력

첫째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력한다.

 

접근 방식

이분 탐색 알고리즘 자체는 어렵지 않지만 이분 탐색 알고리즘 문제들은 정말 어렵다..

특히 이 문제가 정말 이해가 가지 않았다

어떤 걸 이분탐색으로 구해야 하는지 감도 안왔던 문제...

차근차근 풀어보도록 하자..

 

먼저, 가장 마지막 아이가 타게 되는 놀이기구를 구해야하므로!

가장 마지막 아이까지 탑승한 시간을 구해야 한다

즉, 마지막 아이까지 탑승한 시간을 이분탐색으로 구해야한다.

 

최소값은 0, 최댓값은 가장 오래걸리는 놀이 기구를 N번(아이들의 개수)만큼 타는 경우다.

이분 탐색을 돌리면서 해당 시간에 탈 수 있는 아이들의 갯수를 구한 후 더해주고

그 갯수가 N보다 크거나 같면 high = mid-1

크지 않으면 low=mid+1

을 해준다.

 

문제 속 예제 2번을 가지고 풀어본다고 가정하면

N은 7, M은 2이고 놀이기구는 3,2가 있다

이때 high = N * (가장 오래걸리는 놀이기구의 시간) 이므로 21이 된다.

(0,21) 범위에서 이분탐색을 진행하게 되면

(0,21) => (0,9) => (5,9) => (5,6) => (6,6) 의 범위를 갖게되고

즉, 마지막 아이까지 탑승하는 시간은 6초이다

여기서 주의할 점은 아이들의 갯수를 초기화할때 무조건 M번으로 초기화해주어야 한다

처음 0초에서 빈 놀이기구만큼 아이들이 탑승하기 때문!

 

그 후, 마지막 탑승 시점까지 몇번째 아이들까지 탑승했는지 구해준다!

이걸 해주는 이유는 마지막 탑승 시점에 꼭 마지막 아이만 탑승했을 거라는 보장은 없기때문!

구해주는 방법은 (시간-1)을 놀이기구의 시간만큼 나눠준 값을 더해주면 된다

여기서는 5/3 + 5/2 = 3 + 2 (M) = 5이다.

즉, 5초까지 5번째 아이까지 모두 탑승해 있다는 것

 

 

그 후 시간을 놀이기구로 나누면서 마지막 아이가 탑승한 놀이기구를 구해주면 된다!

6번, 7번아이들만 남았기 때문에 

현재 6초에서 놀이기구 3, 놀이기구 2가 나눠지는 지 확인 후 (나눠져야 이미 탑승한 아이들이 내린것)

아이들의 개수를 ++ 해주고 그 갯수가 N이면 놀이기구를 리턴해준다!

 

코드

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll N,M; 
vector<int> v;

int sol() {

    ll low = 0;
    ll high =*max_element(v.begin(), v.end()) * N; //최악의 경우 가장 오래걸리는 놀이 기구만을 N번 탑승한 경우
    ll res = 0;

    while(low <= high) {
        ll mid = (low + high) / 2;
        ll kids = M;

        for(int i=0; i<M; i++) { //각 놀이기구가 mid 시간 동안 몇명의 아이들을 태울 수 있는지 계산
            kids += mid / v[i];
        }

        if(kids >= N) {
            res = mid;
            high = mid - 1;
        }else low = mid + 1;
    }
    

	//마지막 탑승 시간 전까지 몇명의 아이들까지 탑승했는지 구함
    ll k = M;
    for(auto t : v) {
        k += (res - 1) / t;
    }

	//마지막 아이가 탑승한 놀이기구의 번호 구함
    for(int i=0; i<M; i++) {
        if(res % v[i] == 0) k++;
        if(k == N) return i+1;
    }
    return -1;


}

int main() {
    cin>>N>>M;

    for(int i=0; i<M; i++) {
        int x; cin>>x;
        v.push_back(x);
    }

    if(N <= M) {
        cout<<N;
        return 0;
    }

    
    cout<<sol();
}

 

 

정말 어려운 문제고 이해하는데 오랜 시간이 걸렸다..