[C++] BOJ 1561 - 놀이 공원

BOJ 1561 - 놀이 공원 (https://www.acmicpc.net/problem/1561)

 

01. 🔎 문제 탐색

INPUT
N: 아이들의 수 (1 <= N <= 2e9)
M: 1인승 놀이기구의 수 (1 <= M <= 10,000)
놀이기구의 운행 시간이 순서대로 M개가 주어짐 (운행 시간은 1 ~ 30의 범위)

 

• 운행 시간이 지나면, 탑승 중인 아이는 내림
• 놀이기구가 비었으면 가장 앞에 있는 아이가 탑승
• 여러 개가 동시에 비었으면, 더 작은 번호의 놀이기구에 먼저 탑승

 

* 마지막 아이가 탑승하게 되는 놀이기구의 번호를 출력

01-1. 가능한 시간 복잡도

• 아이를 기준으로 순서대로 처리하는 시뮬레이션의 경우, O(N * M)으로 최악의 경우, 1e4 * 2e9회 연산으로 시간초과
• 이분 탐색으로 탑승 시간을 계산하여, 특정 시간에 대한 총 탑승 인원을 계산할 경우, O(M log N)으로 최악의 경우에도 통과

01-2. 알고리즘 선택

• 이분 탐색을 이용하여 특정 시간을 구함 (최대 시간은 30 * 2e9)
  
  • 나온 시간을 바탕으로 해당 시간에 탑승하게 될 총 인원과 N번째 아이가 몇 번째 놀이기구에 탑승할 것인지 알 수 있음

02. 📝 코드 설계하기

1. N, M, v(각 놀이기구의 운행 시간을 담은 배열)을 입력
2. 탑승 시간에 대하여 이분 탐색 수행
   1. 해당 시간에 탑승할 수 있는 총 인원을 계산
   2. 만약, 총 인원이 N보다 작을 경우, left를 mid + 1로 하고 탐색을 계속
   3. 총 인원이 N보다 같거나 클 경우, right를 mid - 1로 하고 탐색을 계속
3. 이분 탐색이 끝나면, (left-1 시간의 총 인원) < N <= (left 시간의 총 인원) 이 되어있을 것
4. left-1 시간의 총 인원을 저장하고, left 시간에 비어있는 놀이기구 개수를 새며, 이전 시간의 총 인원에 더해줌
5. 이전 시간의 총 인원이 N이 되었을 때, 현재 탑승하는 놀이기구가 마지막 아이가 탑승하게 될 놀이기구의 번호

03. 🛠️ 시도별 수정

1회차

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, M;
vector<int> v(1e4+1);

ll get_count(ll t){
  if(t < 0) return 0;
  ll count = M;
  for(int i = 1; i <= M; i++) count += (t / v[i]);

  return count;
}

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

  cin >> N >> M;
  for(int i = 1; i <= M; i++) cin >> v[i];

  ll left = 0, right = 30*(2e9);
  while(left <= right){
    ll mid = (left + right) / 2;
    ll count = get_count(mid);

    if(count >= N) right = mid - 1;
    else left = mid + 1;
  }

  ll prev_count = get_count(left - 1);
  for(int i = 1; i <= M; i++){
    if(left % v[i] == 0){
      if(++prev_count == N) cout << i << "\n";
    }
  }

  return 0;
}