[c++] 백준 #1561 놀이공원 (190822)

< 풀이 >

2019/10/08 - [분류 전체보기] - 백준 1939 중량제한 (8.22) 를 풀고 나서 이분 탐색을 어떻게 쓸지 고민하다가 일단 놀이기구의 총 운행시간을 0~max 설정한 후 이분탐색하면서 총 운행시간 안에 탑승하는 어린이들 수를 계산해보고 모든 어린이가 다 탈 수 있는 그런 운행시간을 계산해봤다. 그 이후 운행시간 – 1일 때 어린이 수를 구하고 운행시간을 1 더하고 나서 그 시간에서 나누어 떨어지는 놀이기구가 있으면 어린이 수를 더하고 그 수가 N이 되면 그 때의 인덱스가 마지막 아이가 타는 놀이기구이다.

마지막 아이가 타는 놀이기구를 타기 위해서 계산하는 부분은 내가 알아내진 못했지만 이분 탐색 접근 방법 자체는 잘한 것 같아서 칭찬하자~!

마지막 아이가 타는 놀이기구 = 주어진 운행시간에 시작하는 맨 뒷 놀이기구를 고르면 됨(운행시간이라는 게 맨 마지막에 실행되는 거 기준이라서)

 

< 소스 코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

#define MAX_M 10010

ll N, M;
int amuse[MAX_M];
int idx_of_final_child = 0;
// limit time 안에 아이들을 다 태울 수 있는 가?
ll solve(ll limit){
    ll ret = 0;
    for(int i=0; i<M;i++){
        ll n_child = limit / amuse[i]; // 주어진 시간 동안 i번째 놀이기구가 운행될 수 있는 횟수
        ret += (n_child + 1);
    }
    return ret;
}

int main(){
    cin >> N >> M;
    int max_m = 0;
    for(int i=0; i<M;i++){
        cin >> amuse[i];
        max_m = max(max_m, amuse[i]);
    }
    if (N <= M){
        cout << N << '\n';
        return 0;
    }
    ll low = 0, high = max_m * ceil(N / M); // 몇 분 걸릴까?
    ll mid;
    while(low < high){
        mid = (low + high) / 2;
        ll ans = solve(mid);
        if (ans >= N){
            high = mid;   
        }
        else low = mid + 1;
    }
    // time이 나옴
    ll cnt = solve(low-1);
    for(int i=0; i<M;i++){
        if (low % amuse[i] == 0) cnt++;
        if (cnt == N){
            cout << i + 1 << '\n';
            return 0;
        }
    }
    return 0;
}