BOJ 1561 : 놀이공원

풀이 상세

파라매트릭 서치

풀이 요약

1. 문제에서 중요한 점은 다음과 같다.

   • $r$ 값으로 지정할 최댓값을 찾아야한다.
   • 초기 시작 시 빈 놀이기구에 탑승하는 경우는 시간이 필요하지 않다. 즉 우리가 놀이기구 시간을 통해 구해야 하는 인원의 분량은 $N-M$ 이 된다. 이는 다시 말해, $N$ 이 $M$ 보다 작은 경우는 시간이 전혀 필요하지 않다는 의미이기도 하다.
   • 몇분 째에 모든 인원이 다 채워지는 지를 탐색할 수 있어야 한다. 단 최댓값이 600억 범위이기에 빠른 시간 복잡도를 가진 알고리즘이 적용되어야 한다.

2. 최댓값 찾기는 쉬운편이다. $N$ 의 최대에 $M$ 의 최대인 값을 곱한 600억 이다.

3. 파라매트릭 서치를 통해, 모든 인원이 다 채워지는 경우를 파악해야 한다. 단 초기 0분에 해당 놀이기구만큼의 인원 분량은 제외한 만큼의 시간을 구해야 한다.

4. 테스트 케이스에 따라 다르지만, 반드시 딱 맞는 시간이 찾아지는 경우는 없다. 빈 놀이기구가 존재한 채 마지막 사람이 탈 수도 있는 것이다. 따라서 먼저 모든 인원이 채워지는 최소 시간의 1을 뺀 값으로 돌아가, 남은 인원을 태우면서 0에 도달하는 인덱스를 직접 찾아주는 방식으로 설계했다.

5. 현재 시간에 놀이기구를 탈 수 있는지를 확인하는 것은 현재시간을 놀이기구가 가진 숫자로 나누었을 때 정확히 나누어 떨어지는 경우가 해당 인원을 태울 수 있는 경우이다.

배운점

• 이분 탐색은 <, ≤, ≥, > 의 차이만으로도 답이 확확 바뀌어서 식을 알아도 답 맞추기 어렵다.

#include <iostream>
#include <vector>
using namespace std;
long long N, M, ans;
vector<int> rides;
void input() {
    cin >> N >> M;
    int num;
    for (int i = 0; i < M; i++) {
        cin >> num;
        rides.push_back(num);
    }
}

void solve() {
    // 예외 1: 인원보다 놀이기구 수가 많은 경우
    if (N <= M) {
        ans = N;
        return;
    }
    long long l = 0;
    long long r = 6e10;
    long long mid, temp, ret, total = N-M;
    while (l <= r) {
        mid = (l + r) / 2;
        long long temp = 0;
        for (int i = 0; i < M; i++) {
            temp += mid / rides[i];
						if (temp > total) break;
        }
        if (temp >= total) {
            ret = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    for (int i = 0; i < M; i++) total -= ((ret - 1) / rides[i]);
    for (int i = 0; i < M; i++) {
        if (ret % rides[i] == 0) total--;
        if (total == 0) {
            ans = i + 1;
            return;
        }
    }
}

void output() {
    cout << ans;
}

int main() {
    input();
    solve();
    output();
}