BOJ 1561 놀이 공원

사용한 알고리즘

이분탐색

알고리즘 설명

이분탐색을 이용하여 N명이 모두 타게 되는 시간을 찾는다.
그 시간 전까지 몇명이 타는지 계산한다.
남은 사람을 그 시간에 도착하는 놀이기구의 앞 번호부터 채우고 모든 사람이 채운 그 순간 태운 놀이기구 번호를 출력한다.

풀이

// baekjoon 1561 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_M=10001;
const ll MAX_INF=1LL<<62;

ll N, M, ride[MAX_M];

int main() {
	scanf("%lld%lld", &N, &M);
	if (N <= M) return !printf("%lld\n", N);
	for (int i=0; i<M; i++)
		scanf("%lld", &ride[i]);

// 놀이기구 M개에 N명이 모두 타게 되는 시간을 찾음
	ll left=0, right=MAX_INF;
	while (left < right) {
		ll mid = (left + right) / 2;
		ll num=0;
		for (int i=0; i<M; i++)
			num += mid / ride[i];
		num += M;
		if (num >= N) right = mid;
		else left = mid+1;
	}
// left는 모두 타게 되는 시점이며, left-1초는 남은 사람이 놀이 기구 앞 번호부터 순서대로 타게 된다.
	left--;

// 처음 0초에 탄 사람수 M명
  ll x = M;
// left-1초에 이미 탄 사람수
	for (int i=0; i<M; i++)
		x += left/ride[i];

// 다시 left으로 사람이 놀이기구를 타는 시점
	left++;
	for (int i=0; i<M; i++) {
// 놀이기구를 타는 경우 x를 증가
		if (!(left%ride[i])) x++;
// N명이 모두 탄 경우 그 놀이 기구 번호 출력(실제 번호는 0부터가 아닌 1부터 이기 때문에 i+1)
		if (x == N) return !printf("%d\n", i+1);
	}
	return 0;
}