[백준/BOJ] 백준 1561번 : 놀이 공원

www.acmicpc.net/problem/1561

1561번: 놀이 공원

이분 탐색을 통해 n번째 사람이 놀이기구를 타게 되는 시간을 구한다. 이분 탐색은 해당 시간에 몇 명이 타는지 can_ride_person = m,  can_ride_person += 해당시간 / riding[i] 이런 방식으로 구한다. 그렇게 n번째 사람이 놀이기구를 탄 시간을 구하고 n번째 사람이 타기 직전 시간 (n번째 사람이 탄 시간 -1) 때 놀이 기구를 탄 사람의 수(before_riding_num)를 구한다 그리고 before_riding_num+1번째 사람부터 타게 되는 그 시간에 어떤 놀이기구를 타는지 확인하여 n번째 사람이 타게 되는 놀이 기구를 확인한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m;
vector<int> riding(10001, 0);

long long Find_time() //이분 탐색을 통해 n번째 사람이 놀이기구를 타게되는 시간을 구한다
{
	long long left = 0;
	long long right = (long long)n * (long long)30; //n명의 사람이 놀이기구 하나를 타는데 모두 30분 기다린다고 할때
	long long mid;
	long long ret;

	while (left <= right)
	{
		mid = (left + right) / 2;

		long long can_ride_person = m; //처음 시작할때 놀이기구 개수만큼 타게 된다

		for (int i = 1; i <= m; i++)
			can_ride_person += mid / riding[i]; //각 놀이기구마다 그 시간에 더 탈 수 있는 인원을 더한다

		if (can_ride_person < n)
			left = mid + 1;
		else if (can_ride_person >= n)
		{
			ret = mid;
			right = mid - 1;
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int input;
		cin >> input;

		riding[i] = input;
	}

	if (n <= m) //인원이 놀이기구의 수 이하일때
	{
		cout << n;
		return 0;
	}

	long long n_person_riding_time = Find_time(); //n번째 사람이 탄 시간
	long long before_n_person_riding_time = n_person_riding_time - 1; //n번째 사람이 타기 직전 시간

	//n번째 사람이 타기 직전까지 놀이 기구를 탄 사람의 수를 구한다(무조건 n-1은 아니다라는것 주의) 
	long long before_riding_num = m;
	for (int i = 1; i <= m; i++)
	{
		before_riding_num += (before_n_person_riding_time) / riding[i];
	}

	//before_riding_num+1번째 사람부터 n번째사람 까지 n번째 사람이 타게 되는 그 시간에 어떤 놀이기구를 타는지 확인
	int result;
	long long check_person = before_riding_num + 1;
	for (int i = 1; i <= m; i++)
	{
		if (n_person_riding_time % riding[i] == 0) //n_person_riding_time시간에 맞춰서 타게 되는 놀이 기구일때
		{
			if (check_person == n)
			{
				result = i;
				break;
			}

			else
				check_person++;
		}
	}

	cout << result;

	return 0;
}