[C++]프로그래머스 입국심사

코딩테스트 연습 - 입국심사 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
long long solution(int n, vector<int> times) {
    long long answer = 0;
    long long min = 1;
    long long max = (long long)n *times[0]; //1000000000이 아닌, 더 큰 n * times가 되어야 함(처음 오류의 원인)
    long long mid;
    long long sum;

    while(min <= max)
    {
        mid = (min + max) / 2; //return값
        sum = 0; //통과하는 사람 수
        for(int i = 0; i < times.size() ;i++)
        {
            sum += mid / (long long)times[i];
        }
        if(sum >= n)//6명이 통과해야하는건데 7명이 통과하면
        {
            max = mid - 1;//더 적게통과해야 하므로 max가 작아져야함
            answer = mid;
        }
        else
            min = mid + 1;
    }
    return answer;
}

정말 신박한 문제였다...

테스트케이스가 만약 n 11 /  times 6,7,10 인 경우, 정답은 30이 되는데

이 때 최솟값을 그림으로 나타내면

이렇게 됨.. 그냥 주어진 times를 순서대로 나타낼수있는만큼 할당하다가 처음으로 그 숫자가 11(N)이 되는 경우가 답이 되는 것임

 

이거를 어떻게 이분탐색으로 나타낼까?

궁금했는데..

위 그림에서 6 창구에는 사람이 4명 온다.

7창구에는 사람이 4명

10창구에는 사람이 3명 옴.

합하면 11.

결국 우리는 answer라는 것을 이동시키면서 얘네의 몫의 합이 n과 같으면

answer를 어거지로 끼워맞추는 그런...느낌이 되는것임.

 

정답을 왔다갔다 끌고다닌다고 할 수 있겠다...

 

만약에 몫이 겹치면요?

상관없음

그만큼 몫이 다른데 추가되겠지

만약에 n = 4, times = 6,12로 이뤄져있다면

6 12 18 24일테고

6창구 * 4가 되든 12 * 2가 되든 어차피 이진탐색은

조건을 만족시키는 동시에 가장 작은값을 찾게해주는 애기 때문에..

통과해되어야하는 사람은 정해져있기 때문에

6 * 4와 12 * 4를 비교하겠지..