백준 BOJ 1561 - 놀이 공원

https://www.acmicpc.net/problem/1561

1561번: 놀이 공원

이분 탐색 문제.

N이 터무니 없이 큰 숫자라서 시뮬레이션 문제로 보면 시간초과를 피할 수 없다.

이분탐색을 통해서 "사람 N명이 탑승하는데 필요한 최소의 시간" 을 구한다.

 

이 시간을 T라고 하면, 정확히 T 시간에 사람이 N명 탑승하게 될 것이므로,

T-1 시간에는 탑승을 하지 못한 사람들이 생기게 된다.

 

이 사람들 중에서 마지막 아이가 나오게 되므로,

T-1 시간에 대해서만 순회해가면서 한명씩 수동으로 탑승시키면 된다.

탑승시켜서 딱 N명이 되는 경우가 마지막 아이인 경우이므로, 이때 정답을 출력한다.

 

모두가 탑승하는데 최대 N*M, 60,000,000,000 만큼이 걸리게 되므로

이분탐색의 끝값을 위 숫자로 잡아주자.

당연하지만 저 숫자는 int범위 바깥으로 넘어가니 long long 으로 선언해주어야 한다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll arr[12345] = {0};
ll N,M;

ll search(ll s, ll e){
	ll mid = (s+e)/2;
	
	if(s==e) return mid;
	
	ll cnt = M;
	for(int i=0; i<M; i++) cnt += mid/arr[i];
	
	if(cnt >= N) return search(s,mid);
	else return search(mid+1,e);
}

int main(){
	cin >> N >> M;
	for(int i=0; i<M; i++){
		cin >> arr[i];
	}
	
	if(N <= M){
		cout << N;
		return 0;
	} 
	
	ll ret = search(1, 60000000000LL);
	ll cnt = M;
	
	for(int i=0; i<M; i++) cnt += (ret-1)/arr[i];
	for(int i=0; i<M; i++){
		if(ret % arr[i] == 0) cnt++;
		if(cnt == N){
			cout << i+1;
			return 0;
		}
	}
}