[백준 c++] 1561 놀이 공원

문제

https://www.acmicpc.net/problem/1561
N명이 한 줄로 줄을 서서 1인승 놀이기구를 타려고 한다.
놀이기구는 총 M종류고 각각 운행시간이 있다.
이 때 가장 마지막 아이가 탑승할 놀이기구의 번호를 구하는 문제다.

풀이

좀 어려웠다😥 그리고 범위 설정때문에 헷갈렸다.
이분 탐색을 이용해서 마지막 아이가 탑승하는 초를 구한다.

만약 운행시간이 3초인 놀이기구, 5초인 놀이기구가 있다면 3번째 아이는 몇 초에 탑승할까?
우선 1,2 번째 아이가 각 놀이기구에 탔을테니 3번 째 아이가 탑승하는 초를 x라고 한다면
2 + x/3 + x/5 == 3
즉 3번 째 아이는 3초에 탑승한다.

2 + x/3 + x/5 == 4
4번째 아이가 탑승하는 초는? 5초

그런데 동시에 여러 놀이기구가 빌 경우가 생기고 해당 초에 앞에 선 아이도 동시에 탑승할 수 있다.
따라서 x-1초까지 탑승을 완료한 아이의 수 tmp를 세주고,
놀이기구를 순회하며 x % a[i] == 0이면 tmp++
if(tmp == n)이면 드디어 마지막 아이가 탑승한 것이므로 그 때의 놀이기구 번호를 출력한다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, a[10001];
long long res;
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        cin >> a[i];
    if (n <= m)
    {
        cout << n << "\n";
        return 0;
    }
    long long hi = 60000000004, lo = 0;
    while (lo <= hi)
    {
        long long mid = (lo + hi) / 2;
        long long cnt = m;
        for (int i = 0; i < m; i++)
        {
            cnt += mid / a[i];
        }
        if (cnt >= n)
        {
            hi = mid - 1;
            res = mid;
        }
        else
        {
            lo = mid + 1;
        }
    }
    long long tmp = m;
    for (int i = 0; i < m; i++)
        tmp += ((res - 1) / a[i]);
    for (int i = 0; i < m; i++)
    {
        if (res % a[i] == 0)
            tmp++;
        if (tmp == n)
        {
            cout << i + 1 << "\n";
            break;
        }
    }

    return 0;
}