[백준 1561] 놀이 공원 (C++)

문제 링크: www.acmicpc.net/problem/1561

1561번: 놀이 공원

1. 주의할 점

- N <= M인 경우?

- 이분탐색을 사용한다

 

2. 구현

- 각 놀이기구의 소요시간을 Arr[] 배열에 입력 받는다

- Num<=Play인 경우, Num을 출력한다

- R은 N의 최대 경우 + 기구 1개 + 소요시간 30분으로 설정한다. 이때, 계산식이 int의 범위를 벗어나므로 (Long Long)으로 형변환한다

 

[아래 내용부턴 이해가 필요 - 아래 TC 참고]

#TC 1 
22 5
1 2 3 4 5



1	2	3	4	5	- 놀이기구 번호

1	2	3	4	5	- 놀이기구를 타고 있는 아이의 번호(시작: 0)
6	2	3	4	5
7	8	3	4	5
9	8	10	4	5
11	12	10	13	5
14	12	10	13	15
16	17	18	13	15
19	17	18	13	15
20	21	18	22

- 이분탐색을 통해 마지막 아이가 탑승한 시간을 구한다

- Result 시간에 Num번째 아이가 놀이기구에 탑승하고 있으므로, Result-1 시간에 몇명의 아이들이 놀이기구를 탔는지 Sum에 더한다

- Result 시간에 새로 타는 아이들의 수를 확인하여, 새로 타는 아이가 있다면 Sum++한다. Sum==Num일 경우, i를 출력한다

 

#include <iostream>
using namespace std;
long long arr[10001];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num,play,idx;
    cin>>num>>play;
    for(int i=1;i<=play;i++)
        cin>>arr[i];
    if(num<=play){
        cout<<num;
        return 0;
    }
    
    long long l=0,r=2000000000LL*30LL,mid,result,sum;
    while(l<=r){
        //초기화
        sum=play;
        mid = l + (r-l)/2;
        for(int i=1;i<=play;i++)
            sum+=(mid/arr[i]);
        if(sum < num) l = mid+1;
        else if(sum >= num){
            result = mid;
            r = mid-1;
        }
    }
    
    //Result초에 탄다 -> 바로 직전 초에 몇명의 아이들이 탔는지 확인
    sum=play;
    for(int i=1;i<=play;i++)
        sum+=(result-1)/arr[i];
    
    //Result초에 새로 타기 시작하는 아이들 확인
    for(int i=1;i<=play;i++){
        if(result%arr[i]==0){
            sum++;
            if(sum==num){
                cout<<i;
                break;
            }
        }
    }
    return 0;
}