프로그래머스 3단계 입국심사 (C++)

핸드폰 하다 잘 거 같아서 그럴 바엔 문제 좀 풀라고 노트북 켰다.
프로그래머스 3단계 4문제를 50분만에 털다니....
반 년 넘게 매달린 보람이 있는 거 같기도 하고 ㅠㅠ
엄청난 발전이긴하다... 1년 더 빡세게 하면 나도 괴물이 될 수 있을까...?

문제링크

https://programmers.co.kr/learn/courses/30/lessons/43238

설명

아마 이분 탐색 문제는 당분간 업로드 하지 않을 거 같다.
이 문제도 이분 탐색이다. 이분 탐색은 기준을 잡는 것이 굉장히 중요하다.

이 문제에서의 기준은 시간이다.
시간을 줄이고 늘려가면서 그 시간 안에 몇 명의 사람들이 심사대를 통과할 수 있는 지 세어주고 많다면 시간을 줄여주고 적다면 시간을 늘려주면서 답을 구한다.

end를 나처럼 극단적으로 잡을 필요는 없고 times에서 가장 큰 값과 n을 곱한 값으로 설정해도 상관 없다.

오히려 저렇게 한다면 시간을 더 절약할 수 있다.
근데 이 부분에서 새로운 사실을 알아냈다. int * int로는 long long을 나타낼 수는 없지만 long long * int로는 long long을 나타낼 수 있다는 점이다! 설마 이거 기본인가...? 무지성 돌진한 나한테는 매우 신기한 사실이었다... 흠흠...

아직 이분 탐색 문제를 많이 풀지는 않았지만 지금까지 풀어 본 바로는 많이 어려운 문제가 아니라면 기준을 찾아내면 대부분 끝나는 거 같다.

코드

#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
    long long start = 0;
    long long end = 1000000000000000000;
    long long mcnt = end;
    while (start <= end)
    {
        long long cnt = 0;
        long long mid = (start + end) / 2;
        for (int i = 0; i < times.size(); i++)
            cnt += mid / times[i];
        if (cnt >= n)
        {
            mcnt = min(mid, mcnt);
            end = mid - 1;
        }
        else
            start = mid + 1;
    }
    return mcnt;
}