[12842] 튀김 소보루

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

흠.. 딱 보자마자!

이분탐색이 떠올랐습니다.

왜냐하면.. 그만큼 빵을 먹는데 걸린 시간을 알아야 한다고 생각했기 때문입니다.

그래서 이분 탐색으로 빵을 먹는데 걸린 가장 근접한 시간을 구합니다.

그거까진 어렵지 않았는데..

문제는

누가 먹었는지 유추하는 부분이었습니다.

문제의 예제를 보면

3명이 25개를 먹는데 걸리는 시간은 15초가 걸립니다.

그 이유는

1번은 1초

2번은 3초

3번은 5초라고 입력이 들어왔는데

15초면 1번은 16개를 먹을 수 있고

2번은 6개

3번은 4개

이렇게해서 총 26개를 먹을 수 있습니다.

1000-975는 25인데 26개를 먹으면 안되지 않나요??

네 맞습니당!

25개만 먹어야합니다.

그러면 14초를 한번 예로 들어볼까요

1번은 15개

2번은 5개

3번은 3개 

이렇게 총 23개를 먹을 수 있죠

그렇기 때문에 가장 근접한 시간은 15초입니다.

여기서 저는 나머지를 이용하여 해당 시간에 가장 근접한 집합을 구했습니다.

15초일 때 가장 근접한 집합은 1,2,3번 셋다 가능합니다.

3명 다 먹는 시간이 나누어 떨어지기 때문입니다.

그래서 15초에 총 먹은 수 26개에서 우리가 25개를 빼고

그 집합의 끝에서 찾아보면 답을 얻을 수 있습니다.

집합의 크기는 3(1, 2, 3) 그리고 15초에 먹은 수 26 - 우리가 구해야하는 수 25

1이 나오죠!

집합의 오른쪽부터 1이동한 정답은 2가 됩니다!

#include <iostream>
#include <string>
#include <vector>
#include <queue>
 
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int t[(int)1e5];
 
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, tmp;
    cin >> n >> tmp;
    n -= tmp;
 
    int k;
    cin >> k;
 
    for (int i = 0; i < k; i++) {
        cin >> t[i];
    }
 
    int left = 0, right = 1e5;
 
    while (left <= right) {
        int mid = (left + right) / 2;
        int eat = 0;
 
        for (int i = 0; i < k; i++) {
            eat += mid / t[i] + 1;
        }
 
        if (eat >= n) right = mid - 1;
        else left = mid + 1;
    }
 
    //left시간
    vi ret;
    int sum = 0;
    int v = 1e3; // 가장 근접한 나머지 값
 
    for (int i = 0; i < k; i++) {
        int rest = left % t[i];
        sum += left / t[i] + 1;
 
        if (rest < v) {
            ret.clear();
            ret.push_back(i + 1);
            v = rest;
        }
        else if (rest == v) ret.push_back(i + 1);
    }
 
    sum -= n; // left초 동안 먹은 빵의 양에서 우리가 구하고자 하는 빵의 양을 뺌
 
    cout << ret[ret.size() - 1 - sum]; // 백터의 끝에서 sum을 빼주면 답을 얻을 수 있음.
 
    return 0;
}