입국심사_3079

문제

상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.

가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.

상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.

예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자. 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다. 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다. 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다. 20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다. 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.

상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)

다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)

출력

첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다.

예제 1

예제 입력 1

2 6
7
10

예제 출력 1

28

예제 2

예제 입력 2

7 10
3
8
3
6
9
2
4

예제 출력 2

8

문제 접근

M명의 인원이 N개의 입국심사대를 거쳐 모두가 심사를 마치는데에 필요한 시간의 최소값을 구하는 문제이다.

그리디 혹은 브루트포스로 문제를 풀게되면, 인원 수 M 의 최대 크기가 10억이기 때문에 반드시 시간초과로 틀리게 된다.

따라서 탐색 범위 축소를 반복하여 원하는 값을 효율적으로 찾는 알고리즘을 선택해야 하는데 이분탐색으로 접근해보았다.

이분탐색을 이용하여 문제를 풀기 위해 심사대에서 한명이 심사를 받는 최소 시간을 l,
심사대에서 m 명이 심사를 받는 최대 시간을 r 로 정하였다.

min_time = min(arr)
max_time = max(arr) * m

또한 이분탐색의 특성상 계속해서 찾고자 하는 값이 나올 때까지 중간 값의 선택과 탐색 범위 축소하고 while문을 통해 일정 기준을 넘지 못하면 시간의 범위를 조정해가며 문제의 답을 찾아가는 것이 이분탐색으로 푸는 문제의 핵심 아이디어이다.

이분탐색을 위한 조건은 l이 r보다 작거나 같을 때만 반복한다.
m 명이 심사를 모두 받는 시간을 mid라고 하고, mid = (l + r) // 2 와 같이 설정하였다.

여기서 n개의 심사대의 정보가 있는 arr리스트를 순회하며 mid시간에 i번 심사대에서 받을 수 있는 심사인원을 새로운 변수인 total_people 에 저장했다.

여기서 total값이 m보다 작게 되면 아직 모든 인원이 심사를 받지 못한 상태이므로 mid를 mid + 1로 갱신한다.
만약 total값이 m보다 크다면 모든 인원이 심사를 받은 상태이므로 mid 를 mid-1로 갱신한다.

total값이 m보다 크다면 모든 인원이 심사를 받을 충분한 시간인 것이다.
반복을 돌면서 mid와 ans값을 비교하며 더 작은 값을 ans값으로 갱신한 뒤, r을 mid - 1로 갱신하여 m명이 모두 심사를 받는데 적은 시간이 걸리는지 더 작은 최소시간이 있는지 검사하면

문제를 해결할 수 있다.

풀이 코드

import sys

# 입력 받기
N, M = map(int, sys.stdin.readline().split(' '))
arr = [int(sys.stdin.readline()) for _ in range(N)]

# 초기값 설정
min_time, max_time = min(arr), max(arr) * M
answer = max_time

# 이분 탐색
while min_time <= max_time:
    mid_time = (min_time + max_time) // 2
    total_people = 0  # 일정 시간 안에 심사할 수 있는 사람 수

    # 각 심사대에서의 심사 가능 사람 수 합산
    for time_required in arr:
        total_people += mid_time // time_required

    if total_people >= M:
        # 현재 중간값으로는 모든 사람을 심사할 수 있는 것이므로
        # 더 작은 값에서도 가능한지 확인하기 위해 범위를 왼쪽으로 좁힘
        max_time = mid_time - 1
        answer = min(mid_time, answer)
    else:
        # 현재 중간값으로는 모든 사람을 심사하기에는 부족하므로
        # 더 큰 값에서 시도해보기 위해 범위를 오른쪽으로 좁힘
        min_time = mid_time + 1

print(answer)