백준 1561번: 놀이 공원

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

1561번: 놀이 공원

으아 이 문제 이분탐색임을 알고 접근 함에도 불구하고 도대체 뭘 기준으로 잡고 해야할지 감이 안잡혔다. n명이 범위가 커서 n명을 기준으로 탐색할려 해도 답이 안나왔기 때문이다..(당연히 안나오지..) 이건 시간 (분)을 기준으로 잡아야한다 그 이유중 하나가 시간이 지남에 따라 n명이 놀이기구 타면서 소모가 되기떄문이다. 즉 시간(분)과 사람 수(명)은 연관이 되어 있다. 놀이기구 타는 데 걸리는 시간을 총 걸리는 시간 분을 나누면 그 놀이기구를 총 걸리는 시간동안 몇명이 탔는지 알 수 있기 때문이다. 예시를 들면

놀이기구 1 , 2 ,3 ,4 ,5 분씩 걸리는 5개 가 있다고 한다. 그리고 총 8분이 지났다고 하면

1) 5+8/1+8/2+8/3+8/4+8/5 =22 명이 탔다.

2) 이 8분이 걸리는 시점에 (8%1==0),(8%2==0),(8%4==0)으로 총 3명이 탔다.

즉 걸리는 총 시간을 기준으로 사람 n명으로 치환해서 시간에 비해 있는 사람을 n명이랑 비교하면서 탐색하면 된다.

코드를 보자.

#include <iostream>
#include <vector>
using namespace std;
int n,m;
long long ed=0;
bool check(vector<long long>& v,long long x){        //x라는 시간을 받고 그 시간동안 놀이기구 이용한 수 cnt,n보다 작으면 참
    long long cnt=m;             //0분에 총 m명 들어갈 수 있다.
    for(int i=0;i<m;i++){
        cnt+=(x/v[i]);
    }
    return cnt<n;
}
int main(){
    cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
    cin >>n>>m;
    vector<long long> v(m);
    for(int i=0;i<m;i++){
        cin >> v[i];
    }
    if(n<=m){               //n명이m개의 놀이기구 보다 작으면 0분걸리므로 그냥 n 출력
        cout << n;
        return 0;
    }
    long long left=0;
    long long right=2000000000LL * 30LL;
    while(left<=right){                //이분탐색 n보다 작으면 참 이므로 mid값은 n이 되기 1분전 시간이 나온다.
        long long mid=(right+left)/2;
        if(check(v,mid)){
            left=mid+1;
            ed=mid;                     //n이 되기 1분전 시간을 ed에 저장
        }
        else{
            right=mid-1;
        }
    } 
    for(int i=0;i<m;i++){                  //n명이 되기 위한 1분이 지날떄 총 몇명이 남는지 확인
        n-=(ed/v[i]);                       
    }
    n-=m;                            //ed+1분이 될 때 n명 수만큼 놀이기구 입장
    int ans=0;
    for(int i=0;i<m;i++){                //n번수 만큼 놀이기구 차례로 탑승
        if(((ed+1)%v[i])==0){
            ans=i;
            n--;
            if(n==0){
                break;
            }
        }
    }
    cout <<ans+1;        
    

}