백준 1561 놀이공원 ❌ (다시 풀어)

CJB_ny·2023년 3월 10일
0

백준

목록 보기
99/104
post-thumbnail

놀이공원


후기

일단 무조건 그림으로 그리자

나한테 가장 잘 맞는 방법인거같다. 팔짱끼고 아무리 생각해도 그림을 그려서 이해하는 것보다 좋은 방법은 없는거같다.

이렇게 1번 2번 3번 놀이기구 순대로 그려보았지만 20억명을 어떻게 나눌지 감이 안잡혔었다.

해답은 시간박스를 놔두어서 해당 시간박스에 1번 2번 3번 순대로 몇번 탈 수 있는지 나누어야함.

코드 분석

Check함수는 초기에는 엄청큰 시간박스를 만든다음에 해당 시간박스안에 마지막 아이까지 놀이기구를 탈 수 있는지 확인하는 로직이다.

이렇게 마지막아이를 태울 수 있는 최소의 시간박스를 만드는 것이다.

cpp

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define endl "\n"
#define ll long long
#define max_n 60000000004
#define MAX_M 10004

ll n, m, a[MAX_M], lo, hi = max_n, ret, mid, temp;

bool Check(ll mi)
{
	temp = m;
	for (ll i = 0; i < m; ++i) temp += (mi / a[i]);
	return temp >= n;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (ll i = 0; i < m; ++i) cin >> a[i];

	// 사람수가 놀이기구 수를 못 따라갈 때
	if (n <= m)
	{
		cout << n << endl;
		return 0;
	}

	// 이분탐색 로직
	while (lo <= hi)
	{
		mid = (lo + hi) / 2;
		if (Check(mid))
		{
			ret = mid; hi = mid - 1;
		}
		else lo = mid + 1;
	}

	// 놀이기구 탈 수 있는지 없는지 가려내는 부분
	temp = m;
	for (ll i = 0; i < m; ++i) temp += ((ret - 1) / a[i]);
	
	for (ll i = 0; i < m; ++i)
	{
		if (ret % a[i] == 0) ++temp;
		if (temp == n)
		{
			cout << i + 1 << endl;
			return 0;
		}
	}

	return 0;
}
profile
공부 일기장으로 변해버린 블로그 (https://cjbworld.tistory.com/ <- 이사중)

0개의 댓글