[c++] 백준 #12842 튀김소보루 (190908)

< 풀이 >

튀김소보루의 갯수가 주어질 때 마지막에 먹은 게 누구인지 맞추는 문제이다. 나는 binary search로 풀었다.

일단 t초동안 먹을 수 있는 튀김소보루의 수를 이분탐색을 통해서 구해서 t 값을 얻은 후,

t-1초동안 먹을 수 있는 소보루 갯수에서 t초까지 하나씩 더해가면서 누가 마지막에 먹었는 지 확인하면 된다. 

 

** 주의할 점 : 먹는 시간은 0초부터(not 1초) 계산된다는 점이다. 계산 식 세울 때 주의.

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
#define pb push_back

ll N, S, M;
vector<ll> eat_time;
    
ll solve(ll t){
    ll ret = 0;
    for(int i=0; i<M;i++){
        ll a = eat_time[i];
        ret += t/a + 1;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> S >> M;
    for(ll i=0; i<M;i++){
        ll a; cin >> a;
        eat_time.pb(a);
    }
    ll low = 0;
    ll high = N-S;
    ll mid;
    ll res = 0;
    while(low <= high){
        mid = (low+high)/2;
        if (solve(mid) >= N-S){
            res = mid;
            high = mid-1;
        }
        else {
            low = mid+1;
        }
    }
    
    ll ans = 0;
    ll n_soboru;
    if (res == 0) n_soboru = 0;
    else n_soboru = solve(res-1); // res-1초 동안 모든 애들이 최대한 먹어버릴 때 값.
    for(int i=1; i<=M;i++){
        if (res % eat_time[i-1] == 0 && n_soboru < N-S){ // (res+1 - 1) 초에 어떻게 먹는 지 보는 거
            ans = i;
            n_soboru++;
        }
    }
    cout << ans << '\n';
    return 0;
}