[C++] 백준(BOJ) - 1561 : 놀이 공원
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.
모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.
놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.
출력
첫째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력한다.
알고리즘
- 이분탐색
풀이
- 이분탐색
- 선형탐색일 때 약 600억의 시간 복잡도 (n <= 20억, 최대 30분)
- 총 시간을 기반으로 이분 탐색
특정 시간이 mid일 때, 10명 이상을 태울 수 있는가?방식으로 접근- 만족하는 res를 찾고 (res-1) 기준으로 tmp 값을 탐색한 후 n과 비교하기
코드
// BOJ-1561 : 놀이 공원
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define max_n 60000000004
#define max_m 10004
ll n, m, a[max_m], l, r = max_n, res, mid, tmp;
bool check(ll mid)
{
tmp = m;
for (int i = 0; i < m; i++) tmp += mid / a[i];
return tmp >= n;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < m; i++) cin >> a[i];
// n이 m보다 적을 때는 그냥 n을 출력 (순차적으로 탑승)
if (n <= m)
{
cout << n;
return 0;
}
// 이분탐색 범위는 시간을 기준으로 한다
// 특정시간이 mid일 때, n명 이상을 태울 수 있는가?
while (l <= r)
{
mid = (l + r) / 2;
if (check(mid))
{
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
// 구한 res보다 직전의 시간 tmp로 이동
tmp = m;
for (int i = 0; i < m; i++) tmp += ((res - 1) / a[i]);
// 순차적으로 하나씩 탐색하여 tmp가 n이 되는 순간 인덱스를 출력
for (int i = 0; i < m; i++)
{
if (res % a[i] == 0) tmp++;
if (tmp == n)
{
cout << i + 1 << '\n';
return 0;
}
}
return 0;
}
평가
- 이분탐색 범위 설정 연습하기
- 직접 탑승 순서를 정하기보다 덩어리로 생각하기
- 시간의 흐름에 따라 탑승 수가 정해진다
