백준 1561 놀이 공원

백준 1561 ←클릭

변수 설정

rmd_sum: t분 후 남아있는 아이의 수 이다.
floor: t = floor와 t=floor+1 사이에서 모든 아이가 탑승함.
left : 이분 탐색의 왼쪽 포인터
right: 이분 탐색의 오른쪽 포인터
mid: 이분 탐색을 위한 중간 포인터

아이디어

• N <= M인 경우 N을 출력한다. (한바퀴도 안돌기 때문)
  
  
• left와 right를 1로 설정하고 right분 이후에는 모든 아이가 탑승을 완료 할 때까지 right를 2씩 곱한다.
  
  
• 이분 탐색을 통해 정확히 몇분에 아이들이 모두 탑승하는지 찾는다.

예시

rmd_sum(t)는 t분 후 아이들이 총 몇명을 탔는지 return 하도록 한다.
만약 rmd_sum(t1)이 N보다 크다면 t1분 에서는 이미 모든 아이들이 탑승을 완료했다는 뜻이 된다.
만약 rmd_sum(t2)이 N보다 작다면 t2분 에는 아직 아이들이 모두 놀이기구에 탑승하지 않았다는 뜻이 된다.
고로 우리가 구할 floor는 t2 <= floor <= t1에 위치한다.
고로 t1과 t2사이의 범위를 절반으로 줄여가면 정확한 floor의 위치를 탐색해야 한다.

코드

github

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

vector<int> ins;
int N, M ,sum = 0; //N: 아이들 수, M: 놀이 기구 수
bool print = false;
int rmd_sum(int a) {
	int rmd = 0;
	
	for (int i = 0; i < ins.size(); i++) {
		rmd += a / ins[i];
	}
	if (print) cout << "remainder of " << a << ": " << rmd + M<< endl;
	return rmd + M;
}

int get_rst(int floor) {
	vector<int> Q;
	for (int i = 0; i < ins.size(); i++) {
		if (floor % ins[i] == 0) {
			Q.push_back(i);
		}
	}
	
	return Q[Q.size() - rmd_sum(floor) + N - 1];
}

int main() {
	freopen("input/1561_input.txt", "r", stdin);
	cin >> N >> M;
	int num;
	for (int i = 0; i < M; i++) {
		cin >> num;
		sum += num;
		ins.push_back(num);
	}
	if (N <= M) { //case 1
		cout << N << endl;
		return 0;
	}
	else { // case 2
		int left = 1, right = 1;
		while (rmd_sum(right) <= N) {
			if(print)cout << "right: " << right << endl;
			right *= 2;
		}
		if (print)cout << "final right: " << right << endl;
		int floor = 0;
		while (left < right) {
			if (rmd_sum(left) == N) {
				floor = left;
				break;
			}
			else if (rmd_sum(right) == N){
				floor = right;
				break;
			}
			int mid = (left + right) / 2;
			if (print)cout << "left: " << left << " right: " << right << " mid: " << mid << endl;
			if (rmd_sum(mid) == N) {
				floor = mid;
				break;
			}
			if (rmd_sum(mid) <= N) left = mid;
			else right = mid;
		}
		if (print)cout << "floor: " << floor << endl;
		while (rmd_sum(floor-1)==N) {
			floor--;
		}
		cout << get_rst(floor) + 1<< endl;
 	}
	return 0;
}

정답~.~