[DAY96] Algorithm : Immigration

입국심사를 기다리는 거대한 인원($10^9$명)을 처리하기 위한 최소 시간을 구하는 문제다. 대기 인원수가 너무 많아 시뮬레이션은 불가능하다. 대신 "특정 시간($T$)이 주어졌을 때 $N$명을 처리할 수 있는가?"를 확인하는 파라메트릭 서치(Parametric Search) 방식을 사용하여 효율적으로 정답을 찾아낸다.

---

❓ 문제 분석

• 목표: 모든 사람이 심사를 마치는 데 걸리는 시간의 최솟값 구하기.
• 제약 조건:
  • 대기 인원 $N$: 최대 10억 명 ($10^9$)
  • 심사 시간: 최대 10억 분 ($10^9$)
  • 최악의 경우(가장 느린 심사관이 모두 처리) $10^{18}$분이 걸릴 수 있으므로, 시간 복잡도는 $O(\log T)$여야 하며 자료형은 long long을 써야 한다.
• 핵심 키워드: "최솟값", "10억 명", "기다렸다가 심사" $\rightarrow$ 이분 탐색

---

💡 풀이 설계

1. 시도했던 접근 (Simulation)

• 처음엔 우선순위 큐를 이용해 심사가 끝나는 대로 사람을 배정하려 했다.
• 하지만 $N$이 10억이라 시간 초과가 발생한다.

2. 최종 해결책 (Parametric Search)

• 발상의 전환: 시간을 기준으로 이분 탐색을 진행한다.
• 범위 설정:
  • left: 1분 (최소)
  • right: 가장 느린 심사관의 시간 $\times N$ (최악의 경우)
• 결정 함수 (Check Logic):
  • 주어진 시간 mid 동안 각 심사관이 처리할 수 있는 인원수(mid / times[i])를 모두 더한다.
  • 합계가 $N$보다 크거나 같다면? $\rightarrow$ 시간이 충분함. 정답 후보로 저장하고 시간을 줄여본다 (right 감소).
  • 합계가 $N$보다 작다면? $\rightarrow$ 시간이 부족함. 시간을 늘린다 (left 증가).

---

💻 코드 구현

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    
    // 탐색 범위 설정
    // 최악의 경우: 가장 오래 걸리는 심사관이 n명을 모두 처리하는 경우
    // times 안에 있는 값 중 최댓값을 구해서 n을 곱한다.
    long long max_time = *max_element(times.begin(), times.end());
    long long left = 1;
    long long right = max_time * n; 
    
    // 이분 탐색 (Binary Search)
    while (left <= right) {
        long long mid = (left + right) / 2;
        long long count = 0;
        
        // 결정 로직: mid 시간 동안 몇 명을 심사할 수 있는가?
        for (int t : times) {
            count += mid / t;
            
            // 오버플로우 방지: 이미 n명을 넘겼다면 더 계산할 필요 없음 
            if (count >= n) break;
        }
        
        if (count >= n) {
            // n명 이상 처리가 가능하다면, 시간이 넉넉하다는 뜻
            answer = mid;    // 현재 시간을 정답 후보로 저장
            right = mid - 1;
        } else {
            // n명을 처리 못 한다면, 시간이 부족하다는 뜻
            left = mid + 1;
        }
    }
    
    return answer;
}

---

🐛 시행착오 및 디버깅

• 자료형 실수: 처음엔 습관적으로 int를 썼으나, $10억 \times 10억 = 100경$이 되어 오버플로우가 발생할 수 있음을 깨닫고 long long으로 수정했다.
• 오버플로우 방지: count를 계산할 때도 숫자가 매우 커질 수 있다. 루프 안에서 count >= n이 되면 즉시 break를 걸어주어 불필요한 연산과 잠재적인 오버플로우를 막았다.

---

✅ 오늘의 회고

항목	내용
유형	이분 탐색 (Binary Search), 파라메트릭 서치
체감 난이도	중 (이분 탐색의 기준을 '시간'으로 잡는 것이 핵심)
복잡도	시간: $O(M \log T)$ ($M$: 심사관 수, $T$: 가능한 최대 시간)
새로 배운 것	입력값이 10억 단위일 때는 주저 없이 $O(\log N)$ 알고리즘을 떠올려야 하며, long long 사용이 필수적이다.