[백준 3079] 입국심사 (C++)

A. 문제설명

 

www.acmicpc.net/problem/3079

3079번: 입국심사

문제에 대한 자세한 설명은 링크 참조

 

1. 상근이와 친구들이 입국심사를 받음

2. 총 인원은 M명, 입국심사대는 N개 주어짐

3. 한 심사대에서는 한번에 한명씩 심사가 가능하며, 각 심사대는 심사소요 시간이 각각 다름

4. 각 인원별 심사 소요시간을 최소로 하여 총 심사 소요시간 중 최소가 되는 것을 구하라

 

B. 접근법

이분 탐색

 

먼저 문제의 조건을 확인하면, 주어진 메모리 제약과 함께 절대로 완전탐색으로 풀이할 수 없는 문제이다.

1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000

1 ≤ Tk ≤ 10^9

 

따라서 이를 위해 연산의 가지치기를 하고, 가장 보편적인 이분 탐색을 적용한다. 문제에서 찾고자하는 심사종료 시간을 최저와 최고 시간안에서 심사대별 인원수가 맞아 떨어지는 구간의 해를 찾는 목표로 탐사한다.

 

C. 풀이

1. 벡터 T를 정렬

2. 심사종료 시간을 이분 탐색

3. sum이 친구들 수(M)가 되는 구간에 도달할 때까지 탐사

4. sum은 이분 탐색 변수 mid를 기준값으로 각 심사대에서 해당 시간만큼 다룰 수 있는 고객 수(나누기 몫)를 더함

5. sum이 M보다 크거나 같으면 hi를 mid 아랫 구간으로 탐사

6. sum이 M보다 작으면 lo를 mid 윗 구간으로 탐사

 

D. 내 코드