프로그래머스 이진탐색 입국심사 c++ 풀이

양심고백합니다...  문제 읽었는데 도저히 어떻게 풀지 모르겠어서 구글링 했습니다...

찾아봤는데 이 포스트가 도움이 됐다: hochoon-dev.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC-c

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

특히 이 부분

물론 문제 유형에도 이분 탐색이라고 적혀있지만, 추후 실제 이러한 문제가 어떠한 테스트에 나왔을 때를 생각하여 입력 값의 범위를 먼저 봐야한다. 입국심사를 기다리는 사람이 1,000,000,000명 이하고, 심사하는데 최대 시간도 1,000,000,000분 이하, 심사관도 100,000명 이하이기 때문에 범위과 굉장히 넓다. 그러므로 이진탐색을 한번 생각을 해봐야 한다.

케이스 제한 사항을 보고 어떤 알고리즘을 써야 할지 판단하는거.. 코테에서 도움 될 듯

 

포스트 읽는데 이진탐색이 가물가물 해서 찾아보고 왔다.

start랑 end를 정하고 중간에서 시작해서 찾는게 이진탐색이다... ㅇㄴ 분명 배웠을텐데... 등록금 아깝다.. 아까워...

이진탐색을 찾아보고 나니 어떻게 풀지 좀 감이 잡혀서 코드 짜 봄

long long solution(int n, vector<int> times)
{
    long long answer = 0;
    long long start = 1;
    long long end = *max_element(times.begin(), times.end()) * n;
    long long mid;
    long long people = 0;

    while (start <= end)
    {
        mid = ((end + start) / 2);

        for (int t : times)
            people += mid / t;

        if (n <= people)
        {
            answer = mid;
            end = mid - 1;
        }
        else
            start = mid + 1;
        people = 0;
    }
    return answer;
}

실...패...

시간이 없어서 여기까지,,, 다시 해볼게요ㅜ

 

long long solution(int n, vector<int> times)
{
    long long answer = 0;
    long long start = 1;
    long long end = *max_element(times.begin(), times.end()) * (long long)n;
    long long mid;
    long long people = 0;

    while (start <= end)
    {
        mid = ((end + start) / 2);

        for (int t : times)
            people += mid / t;

        if (n <= people)
        {
            answer = mid;
            end = mid - 1;
        }
        else
            start = mid + 1;
        people = 0;
    }
    return answer;
}

아 진짜 개 빡치 네^^ 삽질 ㅈㄴ 했는데 자료형 문제 였음ㅎㅎ...

n 자료형을 long long으로 바꿨더니 통과 했습니다... ^^