코드카타 문제

---

오늘의 프로그래머스 코드카타 문제는 다음과 같다.
입국심사 - https://school.programmers.co.kr/learn/courses/30/lessons/43238

문제를 요약하자면, 각각 처리 속도가 다른 입국심사대에서 모든 사람이 심사를 마치는 데 필요한 최소 시간을 구하는 문제였다.

입국심사를 기다리는 사람의 수와 한 사람을 심사하는 데 걸리는 시간은 최대 10억까지 주어질 수 있다.

처음에는 각 심사대가 비는 시간을 직접 계산하는 방법을 생각해볼 수 있지만, 사람을 한 명씩 배치한다면 최대 10억 명을 처리해야 한다. 따라서 사람을 기준으로 반복하는 방식으로는 문제를 해결하기 어렵다고 생각했다.

이 문제에서 이분 탐색의 대상은 사람이나 심사대가 아니라 모든 심사가 끝나는 데 걸리는 시간이다.

특정한 시간 mid가 주어졌다고 생각해보자.

한 명을 심사하는 데 k분이 걸리는 심사관은 mid분 동안 다음과 같은 인원을 처리할 수 있다.

mid / k

따라서 모든 심사관이 mid분 동안 처리할 수 있는 사람의 수는 다음과 같다.

(mid / times[0]) + (mid / times[1]) + ...

이 값이 입국심사를 기다리는 사람의 수 n 이상이라면, mid분 안에 모든 사람을 심사할 수 있다는 의미이다.

• 처리할 수 있는 사람이 n명 이상이면 시간을 더 줄여본다.
• 처리할 수 있는 사람이 n명보다 적으면 시간이 부족하므로 시간을 늘린다.

시간이 증가할수록 심사할 수 있는 사람의 수도 감소하지 않기 때문에 이분 탐색을 적용할 수 있었다.

예를 들어 n = 6, times = [7, 10]이라고 생각해보자.

27분 동안 처리할 수 있는 사람은 다음과 같다.

27 / 7 = 3
27 / 10 = 2

총 5명

6명을 모두 처리할 수 없으므로 27분은 부족하다.

반면 28분 동안 처리할 수 있는 사람은 다음과 같다.

28 / 7 = 4
28 / 10 = 2

총 6명

28분에는 6명을 모두 처리할 수 있다. 따라서 모든 사람이 입국심사를 마치는 데 필요한 최소 시간은 28분이다.

이분 탐색의 범위는 다음과 같이 설정했다.

• left는 최소 시간인 0
• right는 최악의 경우인 10억 × 10억

심사관이 한 명이고, 한 사람을 심사하는 데 10억 분이 걸리며, 심사를 받아야 하는 사람도 10억 명이라면 최대 10^18분이 필요할 수 있다.

이 값은 int의 범위를 훨씬 넘어가므로 탐색 범위와 계산 결과는 모두 long long을 사용해야 했다.

long long left = 0;
long long right = (long long)1000000000 * 1000000000;

중간 시간 mid 동안 처리할 수 있는 사람의 수가 n 이상이라면 mid도 정답이 될 수 있으므로 right = mid로 범위를 줄였다.

반대로 처리할 수 있는 사람의 수가 n보다 작다면 mid는 절대로 정답이 될 수 없으므로 left = mid + 1로 이동했다.

if (sum >= n)
{
    right = mid;
}
else
{
    left = mid + 1;
}

반복문이 종료되면 left와 right가 모든 사람을 처리할 수 있는 최소 시간에서 만나게 된다.

여기서 한 가지 주의할 점은 sum의 오버플로우이다.

심사관이 많고 mid가 큰 경우 처리 가능한 사람의 수를 끝까지 더하면 long long의 범위를 넘을 수 있다. 하지만 이 문제에서는 처리 가능한 인원이 n 이상인지 여부만 알면 되므로, sum >= n이 되는 순간 더 이상 합산하지 않아도 된다.

#include <string>
#include <vector>

using namespace std;

long long solution(int n, vector<int> times) {
    long long left = 0;
    long long right = (long long)1000000000 * 1000000000;
    
    while (left < right)
    {
        long long mid = (left + right) / 2;
        long long sum = 0;

        for (int k : times)
        {
            sum += mid / k;

            if (sum >= n)
            {
                break;
            }
        }
        
        if (sum >= n)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }

    return right;
}

심사관의 수를 M, 탐색할 수 있는 최대 시간을 T라고 하면 시간 복잡도는 O(M log T)으로 표기된다.

최대 시간이 10^18이어도 이분 탐색은 약 60번 정도만 반복한다. 이번 문제를 통해 정답 자체가 큰 범위의 숫자일 때, 특정 값이 가능한지를 판별할 수 있다면 그 정답을 이분 탐색할 수 있다는 점을 다시 확인할 수 있었다.