[C/C++] 백준 #3079 입국심사(이분탐색)

백준 온라인 저지 #3079 문제인 “입국심사” 문제는 다음과 같습니다.

문제 개요

• N개의 입국심사대가 있으며, 각 심사대마다 사람을 심사하는 데 걸리는 시간이 다릅니다.
• M명의 사람이 입국심사를 받으려고 기다리고 있습니다.
• 모든 사람이 입국심사를 마치는 데 걸리는 최소 시간을 구하는 문제입니다.

입력

1. 첫째 줄에 N(심사대의 개수)와 M(심사를 받아야 할 사람 수)이 주어집니다.
2. 둘째 줄부터 N개의 줄에 각 심사대에서 한 명을 심사하는 데 걸리는 시간이 주어집니다.

출력

• 모든 사람이 입국심사를 마치는 데 걸리는 최소 시간을 출력합니다.

해결 방법

• 이분 탐색을 활용하여 최소 시간을 구하는 것이 핵심입니다.
• 특정 시간을 기준으로 모든 사람이 심사를 받을 수 있는지 판단하며, 조건을 만족하는 최소 시간을 찾습니다.

이 문제는 이분 탐색과 시간 복잡도를 잘 고려하여 풀어야 하는 대표적인 최적화 문제입니다.

 

immigration

 

제가 작성한 전체 소스입니다.

//----------------------------------------------------------
//    baekjoon #3079 - immigration
//        - by Aubrey Choi
//        - created at 2020-01-14
//----------------------------------------------------------
#include <stdio.h>

int main()
{
    int n, m, i, max=0; static int t[100000];
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++) scanf("%d",t+i),max=(t[i]>max)?t[i]:max;
    long long low=0, high=(long long)max*m/n+max;
    while(low+1<high)
    {
        long long c=(low+high)/2, k=0;
        for(i=0;i<n;i++) k+=c/t[i];
        if(k>=m) high=c; else low=c;
    }
    printf("%lld\n",high);
}

 

이 코드는 이분 탐색을 이용해 최적의 입국심사 시간을 계산합니다. 주요 부분을 단계별로 설명하겠습니다.

코드 설명

1. 변수 초기화

int n, m, i, max=0; static int t[100000];

• n: 입국심사대의 수
• m: 입국심사를 받아야 하는 사람의 수
• max: 가장 오래 걸리는 심사 시간 (최대값 저장용)
• t: 각 심사대에서 한 명을 심사하는 데 걸리는 시간을 저장하는 배열 (최대 크기 100,000)

2. 입력 받기

scanf("%d%d",&n,&m);
for(i=0;i<n;i++) scanf("%d",t+i),max=(t[i]>max)?t[i]:max;

• 첫 번째 scanf로 n과 m 값을 입력받습니다.
• 반복문으로 각 심사대의 심사 시간을 배열 t에 저장합니다.
• 동시에 max 변수를 업데이트하여 가장 큰 심사 시간을 기록합니다.

3. 이분 탐색을 위한 범위 설정

long long low=0, high=(long long)max*m/n+max;

• low는 최저 시간인 0으로 설정됩니다.
• high는 최대 시간의 초기 값을 설정하는데, max * m / n + max를 사용합니다. 이는 최악의 경우를 가정한 시간 상한입니다.
• long long 타입을 사용하여 큰 수를 다룰 수 있도록 합니다.

4. 이분 탐색 알고리즘

while(low+1<high)
{
    long long c=(low+high)/2, k=0;
    for(i=0;i<n;i++) k+=c/t[i];
    if(k>=m) high=c; else low=c;
}

• low + 1 < high 조건이 만족할 때까지 반복합니다. 이는 low와 high의 간격이 좁혀질 때까지 반복하겠다는 뜻입니다.
• c는 현재의 중간값으로, 현재 시간 c 내에 심사를 완료할 수 있는 사람 수를 계산합니다.
• k는 시간 c 동안 심사할 수 있는 사람 수의 총합입니다.
• 각 심사대에서 c / t[i]만큼의 사람을 심사할 수 있으므로 이를 k에 누적하여 더합니다.
• k >= m이면 모든 사람이 심사를 받을 수 있으므로 high를 c로 줄이고, 그렇지 않으면 low를 c로 늘립니다.

5. 결과 출력

printf("%lld\n",high);

• 최종적으로 high에 모든 사람이 입국심사를 받을 수 있는 최소 시간이 저장되므로 이를 출력합니다.

요약

이 코드는 low와 high 범위를 이분 탐색으로 줄여가면서 모든 사람이 입국심사를 받을 수 있는 최소 시간을 찾습니다.