[c++] 백준 1561 놀이공원 (이분 탐색 / binary search)

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

solution

main 함수에서 while 문을 돌면서 이분탐색을 수행한다.
이분탐색을 통해 얻은 최적의 운영시간을 이용하여 마지막 아이가 타러 들어가는 놀이기구 번호를 구해준다.
-> 이 부분에서 결과괎을 어떻게 사용하는지에 대해 블로그를 참고 (https://baebalja.tistory.com/m/158)

시간복잡도
O(log(놀이기구 하나의 운행 시간 * 인원 수의 최대 값))

check 함수

해당 운행시간으로 놀이기구를 운전 할 때, 탑승할 수 있는 인원수를 계산

bool check(long long mid) {
    ll cnt = q;
    for (int i = 0; i < v.size(); i++) {
        cnt += mid / v[i];
    }
    return cnt >= n;
}

전체 코드

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

vector<int> v; // 놀이기구의 운행시간을 저장하는 벡터
vector<int> result1; // 결과 벡터 1
vector<int> result2; // 결과 벡터 2
typedef long long ll; // long long 자료형의 별칭 설정

ll l, h, n, q; // 이분탐색의 범위와 입력 변수 선언

// 주어진 운행시간(mid)으로 놀이기구를 탈 수 있는지 확인하는 함수
bool check(long long mid) {
    ll cnt = q; // cnt 변수에 초기 운행 횟수 할당
    for (int i = 0; i < v.size(); i++) { // 모든 놀이기구에 대해 반복
        cnt += mid / v[i]; // 주어진 시간 동안 각 놀이기구의 운행 횟수 더하기
    }
    return cnt >= n; // 놀이기구 운행 횟수가 요구된 인원 수 이상인지 확인
}

int main() {
    l = 1; // 이분탐색의 시작 범위
    h = 60000000000; // 이분탐색의 끝 범위 (놀이기구 하나의 운행시간 * 인원수의 최대값)
    cin >> n; // 인원 수 입력
    cin >> q; // 놀이기구 수 입력
    for (int i = 0; i < q; i++) { // 모든 놀이기구의 운행시간 입력
        int a;
        cin >> a;
        v.push_back(a); // 놀이기구의 운행시간 벡터에 추가
    }
    if (n <= q) { // 인원 수가 놀이기구 수와 같거나 작은 경우
        cout << n; // 인원 수 출력 후 프로그램 종료
        return 0;
    }
    ll time = 0; // 최적 운행시간 초기화
    while (l <= h) { // 이분탐색 수행
        long long mid = (l + h) / 2; // 중간 값 설정
        if (check(mid)) { // 운행시간이 충분한 경우
            h = mid - 1; // 더 작은 운행시간을 탐색하기 위해 범위 갱신
            time = mid; // 현재 운행시간 저장
        } else {
            l = mid + 1; // 운행시간이 부족한 경우, 더 큰 운행시간을 탐색하기 위해 범위 갱신
        }
    }
    ll ch = q; // 이전 운행 횟수로 초기화
    for (int i = 0; i < q; i++) { // time-1초에 타러간 아이들의 수 계산
        ch += (time - 1) / v[i];
    }
    for (int i = 0; i < q; i++) { // time초에 타러가는 아이들의 수 갱신
        if (time % v[i] == 0) ch++;
        if (ch == n) { // 마지막 아이가 타러 들어가는 놀이기구 번호 출력
            cout << i + 1 << "\n";
            break;
        }
    }
}