백준 1561 C++

처음 이 문제를 보곤 priority_queue가 떠올랐다. 실제로 pq로 구현을 했지만 시간 초과가 나왔었다.

그 다음으로 떠올랐던 방법은 최소 공배수를 구해서 아이들 수에 나누는 방식이었다. 이 방법도 동일하게 시간 초과가 나왔다. 그래서 어떤 방법을 사용해야하는지 감이 잡히지 않아. 다른 글들을 찾아보았고 생각지도 못한 방법으로 문제를 풀었다.

 

일단 n이라는 아이들이 모두 탈 수 있는 최소의 시간을 구한다.

이 n이라는 시간에 몇개의 놀이기구를 탈 줄 모른다. 100개 중 99개를 n이라는 시간에 탑승할 가능성도 있다.

여기서 우린 n번째 아이가 몇번 놀이기구를 탑승하는지 알아야한다.

그래서 최소시간 - 1을 해서 그 전에 몇명이 탔는지 찾아낸다.

 

다음으로 n번째 아이를 찾기 위해서 %연산자를 통해 현재 탈 수 있는 놀이기구인지 확인한 후에 findN을 +1씩하며 몇번째 놀이기구에 탑승했는지 찾아내면 된다. 

 

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

ll n, m;		//아이들 수, 놀이기구의 수
vector<ll> v;
ll lo = 0, hi = 60000000000 + 10, mid;
ll timeMin;

bool check(ll mid)
{
	ll tempN = m;				//처음엔 모두 비어있기 때문에 모든 놀이기구에 태워야한다.
	for (ll i : v) {
		tempN += mid / i;		//mid라는 시간동안 i번째 놀이기구는 몇명이 탈 수 있는가?
	}

	return tempN >= n;		//타야하는 아이보다 값이 크거나 같은가?
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int t;
		cin >> t;
		v.push_back(t);
	}

	if (n <= m) {
		cout << n;
		return 0;
	}

	while (lo <= hi) {
		mid = (lo + hi) / 2;
		if (check(mid)) {
			timeMin = mid;
			hi = mid - 1;		//지금으로 n명을 다 태울 수 있으니 좀 더 좁은 구역으로 가능한 곳을 찾아라.
		}
		else {
			lo = mid + 1;		//지금의 시간으론 n명을 다 태우진 못한다 -> 너 값이 큰 범위로 찾아라
		}
	 }
	
	ll findN = m;
	for (ll i : v) {
		findN += (timeMin - 1) / i;		//현재 timeMin일 때 모든 아이들이 탑승 가능하다. 이 timeMin보다 -1일 경우엔 모든 아이들이 탑승하지 못한다. 이 mid라는 시간에서 어떤 놀이기구를 탑승했는지 찾아야한다. 그렇기에 직전에 몇명이 탔는지 findN에 저장한다.
	}

	for (int i = 0; i < m; i++) {
		if (timeMin % v[i] == 0) {		//나머지가 없다. 즉, 현재 i번째 놀이기구는 탑승이 가능한 상태이다. 
			findN += 1;
		}

		if (findN == n) {
			//cout << "result : ";
			cout << i + 1;
			break;
		}
	}


}