[백준] 1561번 : 놀이공원

🤔 문제분석

📝 문제요약

아이들(N)과 놀이기구(M)가 주어지고, 각 놀이기구는 한명만 탈 수 있고 운행시간이 주어졌을때 아이들이 순차로 놀이기구를 탄다고 한다면 마지막 아이가 탄 놀이기구의 번호를 구하는 문제이다.

🎯 필요한 개념

• 이분탐색

✅ 알고리즘

1. 아이들을 태울 수 있는 최소 시간을 구한다. ( 이분탐색 )
   1. 놀이기구를 순회하면서 아이들을 태울 수 있는 카운트를 한다.
      1. 시간 / 놀이기구[i]
   2. 아이들을 태울 수 없다면 시간을 줄여본다.
   3. 아이들을 태울 수 있다면 시간을 늘려본다.
2. 해당 시간에 모두 태일 수 있는 아이들을 뺀다.
   1. N -= child_cnt
3. 다음시간에 놀이기구를 탈 수 있는 경우라면 태우고 그렇지 않으면 태우지 않는다.
   1. 다음시간 % 놀이기구[i] == 0 인경우 태울 수 있다.
   2. 그렇지 않은 경우는 태울 수 없는 경우이므로 무시한다.

💻 코드

// <https://www.acmicpc.net/problem/1561>
#include 
#include 
#include 
#include 

long long N;
int M;

using namespace std;
vector plays;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    plays.resize(M);
    for(int i = 0; i < M; i++)
    {
        cin >> plays[i];
    }

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

    N -= M;
 
    long long start = 1;
    long long end = N * M * 30;
    long long cycle = 0;
    long long child_cnt = 0;

    // 시간안에 아이들을 태울 수 있는 횟수를 구한다.
    while(start <= end)
    {
        auto mid = (start + end) / 2;
        long cnt = 0;
        for(int i = 0; i < M; i ++)
        {
            auto v = mid / plays[i];
            cnt += v;
        }

        if (cnt >= N)
        {
            end = mid - 1;
        }
        else
        {
            cycle = mid;
            child_cnt = cnt;
            start = mid + 1;
        }
    }

    N -= child_cnt;
    int idx = 0;
    while(N)
    {
        if((cycle + 1) % plays[idx] == 0) N -= 1;

        idx += 1;
    }

    cout << idx;
    return 0;
}