[BOJ]1561번: 놀이 공원 (c++)

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

1561번: 놀이 공원

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll N_MAX = 2000000000LL;
const ll T_MAX = 30;
ll N, M;

// 주어진 time시간까지 놀이기구를 탄 아이들 수 구하기
ll cnt_passed(vector<ll> &rides, ll time)
{
	// 0분에는 모든 놀이기구가 비어있으므로, sum은 M부터 시작
	ll sum = M;
	for (int i = 0; i < M; ++i)
	{
		// 해당 시각까지 놀이기구를 탄 아이들 수 카운팅
		sum += time / rides[i];
	}
	return sum;
}

void binary_search(vector<ll>& rides, ll &now, ll& passed)
{
	ll left = 0;
	ll right = N_MAX * T_MAX; // 최대 아이들 수 * 최대 놀이기구 시간

	while (left <= right)
	{
		// passed : mid시각까지 놀이기구를 탄 아이들 수
		ll mid = (left + right) / 2;
		ll cnt = cnt_passed(rides, mid);

		if (cnt >= N)
		{
			// now : 마지막 아이가 놀이기구를 타는 시간대
			now = mid;
			right = mid - 1;
		}
		else
		{
			// passed_bf : mid시각 전까지 놀이기구를 탄 아이들 수
			passed = cnt;
			left = mid + 1;
		}
	}
}

int get_ride_num(vector<ll> &rides, ll now, ll passed)
{
	for (int i = 0; i < M; ++i)
	{
		// now에 비어있는 놀이기구가 있다면
		if (now % rides[i] == 0)
		{
			++passed;

			// 놀이기구를 탄 아이들 수가 N이면, 해당 놀이기구 번호 반환
			if (passed == N)
			{
				return i + 1;
			}
		}
	}
	return 0;
}

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

	// 입력
	cin >> N >> M;
	vector<ll> rides(M);
	for (int i = 0; i < M; ++i)
	{
		cin >> rides[i];
	}

	/*
		아이들 수가 놀이기구 수보다 적을 때 
		: 마지막 아이는 N번째 놀이기구를 탄다
	*/
	if (N <= M)
	{
		cout << N;
	}
	else
	{
		/*
			now : 마지막 아이가 놀이기구를 타는 시각
			passed : now 시각 전까지 놀이기구를 탄 아이들 수
			
			이분탐색으로 now와 passed를 구한다
		*/
		ll now = 0, passed = 0;
		binary_search(rides, now, passed);

		cout << get_ride_num(rides, now, passed);
	}
	 
	return 0;
}

 

고통스러운 문제였다ㅜㅜ

이분의 블로그와 백준님의 강의를 참고해서 풀었다.

 

입력값으로 아이들 수 N과 놀이기구 수 M, 그리고 놀이기구 각각의 운행시간이 주어진다.

이때 아이들은 비어있는 놀이기구를 번호 오름차순으로 타야한다.

마지막 아이가 타는 놀이기구를 구하는 것이 문제 요구사항이다.

 

1<= N <= 2,000,000,000
1<= M <= 10,000
운행 시간은 1 이상 30 이하의 자연수

 

수의 범위를 보면... 이분탐색으로 풀어야 함을 알 수 있다.

그런데 이분탐색으로 무엇을 찾아야 할 것인가?

 

 

다음의 예시로 표를 그려보면 아래 그림과 같다. 

17 5
2 2 3 4 5

17번째 아이는 8분에 2번 놀이기구를 고른다

아이들이 놀이기구를 선택하고 난 후, 시간이 지나면

비어있는 놀이기구를 차례로 앞에서부터 선택해 나간다. 

이분탐색으로는 N번째 아이가 놀이기구를 선택하는 시각을 찾아야 한다. 

 

 

표를 그려보면 17번째 아이는 8분에 놀이기구를 선택함을 알 수 있다.

그런데 문제가 있다.

16번째 아이와 18번째 아이도 8분에 놀이기구를 선택한다.

8분이라는 시각을 구한 것만으로는 부족하다.

 

따라서 8분 이전에 이미 놀이기구를 탄 아이 수 passed를 따로 구하고

8분째에 비어있는 놀이기구를 passed 이후부터 카운팅 해주어야 한다. 

 

 

결과적으로 이분탐색을 통해서 구해야 하는 변수는 2개가 되었다.

1. N번째 아이가 놀이기구를 선택하는 시각 now

2. now이전에 놀이기구를 탄 아이들 수 passed

 

이를 위에 예시를 적용해서 그림으로 나타내면 다음과 같다.

passed가 결정되는 시점과 now가 결정되는 시점이 다르다

 

 

보다시피 두 변수가 결정되는 시점에 차이가 있을 수 있으므로,

이분탐색 코드에서 두 변수에 값을 대입하는 위치도 달라야 한다.

now는 mid시각까지 놀이기구를 탄 아이들수가 N보다 같거나 많을때

passed는 N보다 적을때 결정된다.

while (left <= right)
{
    // cnt : mid시각까지 놀이기구를 탄 아이들 수
    ll mid = (left + right) / 2;
    ll cnt = cnt_passed(rides, mid);

    if (cnt >= N)
    {
        // now : 마지막 아이가 놀이기구를 타는 시간대
        now = mid;
        right = mid - 1;
    }
    else
    {
        // passed : mid시각 전까지 놀이기구를 탄 아이들 수
        passed = cnt;
        left = mid + 1;
    }
}