[BAEKJOON] 1561 놀이 공원 (C++)

[ 문제 ]

이분탐색을 아무리많이풀어도 해결책이 금방 나오지않는 기분은 정상이다

더 많이풀고 더 고민하여 빠르게 감을익혀 이분탐색의 중심값을 어떻게 판별할지 찾아내는것을 목표로 해야겠다

 

해당문제에는 파라메트릭 서치(Parametric Search)개념이 추가된다.

위에대해 지식이없다면 링크를통해 살짝 보구오는걸 추천합니당.

문제

N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.

모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.

놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.

출력

첫째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력한다.

[ 조건 및 풀이 ]

(1) 최대범위 : 입력된 아이들의 수 x 놀이기구의 최대시간 or 문제에 주어진 아이들 수의 최대값 x 놀이기구의 최대 시간

int형 숫자 두개를 곱할때, int범위를 벗어나게되면 역행한다
각 숫자에 LL을 붙임으로써 longlong형으로 치환후 곱해준다

(2) 중앙값, 결과값 : 아이들이 놀이기구에 타는 시간

(3) 마지막 아이가 탄 놀이기구의 번호를 찾아야되므로 결과값-1 시간에 대한 놀이기구 운행 회수(=시간까지 아이들이 탄 횟수)를 구하고, 이후 기존 결과값에 대해 첫 놀이기구부터 운행가능여부를 판단하여 운행회수를 증가시켜간다. 이때 이 운행회수가 아이들이 탄 횟수와 동일해질때가 마지막 아이가 탄 놀이기구의 번호가 나오게된다.

[ 핵심소스코드 / C++ ]

조건 (1), (2)

ll solve() {
    ll result = -1;
    ll left = 0, right = 2000000000LL * 30LL;
    while (left <= right) {
        ll mid = (left + right) / 2;
        ll sum = game;
        for (int i = 0; i < game; i++)
            sum += mid / ary[i];
        if (sum >= child) {
            if (sum == child)
                result = mid;
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
    return result;
}

조건 (3)

ll time = solve();
sum = game;
for (int i = 0; i < game; i++)
    sum += (time - 1) / ary[i];
for (int i = 0; i < game; i++) {
    if (time%ary[i] == 0)
        sum++;
    if (sum == child) {
        cout << i + 1;
        return 0;
    }
}

[ 전체소스코드 / C++ ] 

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
using namespace std;
#define ll long long
#define MAX 0

ll child;
int game, temp;

vector<int>ary;

ll solve() {
    ll result = -1;
    ll left = 0, right = 2000000000LL * 30LL;
    while (left <= right) {
        ll mid = (left + right) / 2;
        ll sum = game;
        for (int i = 0; i < game; i++)
            sum += mid / ary[i];
        if (sum >= child) {
            if (sum == child)
                result = mid;
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
    return result;
}
int main() {
#ifdef _CONSOLE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
	
    ll sum = 0;
    cin >> child >> game;
    for (int i = 0; i < game; i++) {
        cin >> temp;
        ary.push_back(temp);
    }
    //놀이기구수보다 아이들수가적을경우 아이디 수를 바로출력
    if (child <= game) {
        cout << child;
        return 0;
    }
    ll time = solve();
    sum = game;
    for (int i = 0; i < game; i++)
        sum += (time - 1) / ary[i];
    for (int i = 0; i < game; i++) {
        if (time%ary[i] == 0)
            sum++;
        if (sum == child) {
            cout << i + 1;
            return 0;
        }
    }
}