[백준][C++] 1561: 놀이 공원

문제

풀이

이분 탐색을 사용한다. 

• 모두 탑승하는데 소모되는 최소 시간을 이분 탐색한다. 
• 최소 시간은 0, 최대 시간은 (N X 최장 운행 시간)으로 설정했다. 
• mid값을 이용해서 해당 시간 동안 몇 명이 탑승할 수 있는 확인한다. 여기서 주의할 점이 0초 때, 이미 기구에 탑승하고 있기 때문에 현재 탑승한 아이의 수를 미리 N으로 세팅해줘야 한다. 
• 이분 탐색으로 얻은 최소시간은, 마지막 아이가 놀이기구에 탑승한 시점의 시간이다. 
• (최소시간 - 1)분 때, 총 몇 명이 탈 수 있는지 확인한다. 
• (최소시간 % 탑승시간 == 0)이라면 해당 놀이기구에는 최소시간 시점에 탑승할 수 있는 놀이기구이다. 인덱스가 작은 순으로 해당 검사를 하면서 총 탑승한 아이의 수가 N과 같을 때의 인덱스를 출력한다.

코드

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

using namespace std;

vector<long long> nums;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    long long maxi = 0;
    for (int i = 0; i < M; ++i)
    {
        long long temp;
        cin >> temp;
        nums.push_back(temp);

        maxi = max(maxi, temp);
    }

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

    long long start = 0;
    long long end = N * maxi;
    long long total_time = 0;
    while (start <= end)
    {
        long long mid = (start + end) / 2;

        // 0초일 때, 놀이기구에 모두 들어가 있으니 current를 M에서 시작
        long long current = M;
        for (int i = 0; i < M; ++i)
        {
            current += (mid / nums[i]);
        }

        if (current < N)
        {
            start = mid + 1;
        }
        else
        {
            total_time = mid;
            end = mid - 1;
        }
    }

    // (최소시간 - 1)분 때, 몇 명이 탈 수 있는지 확인
    long long temp_time = total_time - 1;
    long long ridden = M;
    for (int i = 0; i < M; ++i)
    {
        ridden += (temp_time / nums[i]);
    }

    // 마지막 사람이 몇 번 놀이기구에 들어가는지 확인
    for (int i = 0; i < M; ++i)
    {
        // 최소시간과 탐승 시간이 나누어 떨어진다면, 
        // 최소시간 때에 놀이기구에 탑승할 수 있다.
        if (total_time % nums[i] == 0)
        {
            ridden++;
        }
        if (ridden == N)
        {
            cout << i + 1;
            break;
        }
    }

    return 0;
}