프로그래머스 : 입국심사(lv3) C++

프로그래머스 링크

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

프로그래머스

---

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

using namespace std;

long long solution(int n, vector<int> times)
{
    long long answer = 0;

    // 호춘쿠키님의 글을 보고 적고 공부내용임
    // 주석 걸린내용 대부분 호춘쿠키님의 주석내용(이해가기 쉽게 주석 완벽히 달아놓으셔서 그대로 작성하였고
    // 두 가지 부분만 다르게 생각하여 수정해줌)
    // 1. 호춘쿠키님은 최소 시작값 start변수 값을 1로 주었는데 times[0] * 1이 맞는거 같다고 생각이 들어 수정함.
    // 2. 중간에 cnt값을 구해주는 과정에서 times의 원소값을 longlong으로 형변환 해주어야 될 거 같아서 변경해줌.
	// 호춘쿠키님 출처 : https://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

    // 가장 오래 걸리는 심사관의 시간을 알기 위한 정렬.
    sort(times.begin(), times.end());

    // 시간으로 기준을 두었을 때 최소 => 위에서 정렬을 해주었기 때문에 가장 적은 시간을 
    // 소모하는 심사관의 최소 시간 * 1인데 * 1는 무의미 하기 때문에 생략
    long long start = (long long)times[0];
    // 시간으로 기준 두었을 때 최대 => 심사 시간이 가장 오래 걸리는 사람에게 n명 모두 갔을 때
    long long end = (long long)times[times.size() - 1] * n;
    // 탐색 범위(시간) 기준
    long long mid;

    while (start <= end)
    {
        // 중앙값
        mid = (start + end) / 2;
        // mid 시간동안 심사 처리할 수 있는 모든 사람 수
        long long cnt = 0;

        for (int i = 0; i < times.size(); i++)
        {
            // 각 시간별 mid 시간 동안 처리할 수 있는 사람들 수를 더해준다.
            cnt += mid / (long long)times[i];
        }

        // mid 시간동안 처리할 수 있는 모든 사람 수가 n명 보다 작기 때문에 해당 문제 조건 만족 X
        if (cnt < n)
        {
            // 최소값을 mid + 1 로 좁혀준다.
            start = mid + 1;
        }
        // mid 시간 동안 처리할 수 있는 사람들이 n명 이상으로 해당 문제의 조건을 만족한다면
        else
        {
            // mid(기준 시간) 값이 end(최대 시간) 값 보다 이하면
            // mid 는 최소값이 될 수도 있기 때문에 answer에 넣어주고
            if (mid <= end)
            {
                answer = mid;
            }
            // 최소 값을 찾기 위해 범위를 더 좁혀준다
            end = mid - 1;
        }
    }

    return answer;
}