[백준 1561번 / C++] 놀이 공원

이분 탐색을 통해서 풀어야 할 문제다. 

 

먼저 l과 h 에 최소로 들어갈 숫자 1과 최대로 들어가야할 숫자 60000000000을 저장한다. 

즉, h에는 "놀이기구 하나에 운행시간 30 * 사람수의 최대" 가 들어가야한다. 

내가 이렇게 초기화 안해서 아래 문제에서 매우 화가난적이 있어서 이제는 최대값이 몇인지를 계산부터 한다. 

이 백준문제에서도 h값을 무작정 높은 숫자로 했다가 원하는 결과값이 안나올 수 있으니 초기화에 신경쓰자.

[Level 3] 입국심사 (C++)

---

로직은 이렇다. 

 

애초에 사람수가 놀이기구 수보다 적다면 그냥 바로 사람수가 놀이기구 숫자로 판단해서 출력하면 끝이다. 

 

하지만 사람수가 놀이기구 수보다 많다면 시간에 따른 사람의 수를 구해야한다. 

먼저 주의 해야할 점은 0초일때는 놀이기구에 모두 들어가있으니 이진탐색을 시작할 때 사람수를 카운팅할 때는 미리 놀이기구의 개수를 세팅 해주고 시작하자. 

 

이후 사람의 수가 n값인 time이 저장될 텐데 그 값보다 하나 작은 값을 먼저 비교해야한다. 

예를 들어, 

 

time=50 초로 나왔다. 

그렇다면 먼저 49초에 입장하는 아이들의 수를 먼저 세보자. 

 

이후 50초에 들어가는 아이들의 수를 세면 되는데 

이때 "if( time % 놀이기구시간 ==0 )" 가 이면 이전에 탔던 아이가 나가고 새로운 아이가 들어올 수 있을 때 이다.

그럴때마다 카운트를 해주고 해당 카운트 변수가 n값과 일치하게 된다면 놀이기구 번호 값을 출력하면 된다. 

#include <iostream>
#include <vector>
#include <climits>
using namespace std; 
vector <int> v; 
vector <int> result1; 
vector <int> result2; 
typedef long long ll;
ll l, h, n, q; 
bool check(long long mid) {
	ll cnt = q; 
	for (int i = 0; i < v.size(); i++) {
		cnt += mid / v[i];
	}
	return cnt >= n; 
}
int main() {
	l = 1; h =60000000000; //놀이기구 하나에 운행시간 30 * 사람수 최대
	cin >> n; cin >> q; 
	for (int i = 0; i < q; i++) {
		int a; cin >> a; 
		v.push_back(a); 
	}
	if (n <= q) { //사람수가 놀이기구수와 같거나 작다면 바로 출력
		cout << n; return 0; 
	}
	ll time = 0; 
	while (l <= h) {
		long long mid = (l + h) / 2;
		if (check(mid)) {
			h = mid - 1;
			time = mid; 
		}
		else l = mid + 1; 
	}
	ll ch = q; 
	for (int i = 0; i < q; i++) {// time-1 초에 타러간 아이들 숫자
		ch += (time - 1) / v[i]; 
	}
	for (int i = 0; i < q; i++) { // time초에 타러가는 아이들 숫자 갱신
		if (time % v[i] == 0)ch++; 
		if (ch == n) {//마지막 아이가 타러 들어가는 놀이기구 번호 
			cout << i + 1 << "\n"; break; 
		}
	}
}

 

1561번: 놀이 공원