[BOJ] 3079. 입국심사

3079. 입국심사

문제

입력

• 첫 줄
  • 입국심사대 N개 $(1 \leq N \leq 100,000)$
  • 입국심사를 받을 사람 M명 $(1 \leq M \leq 1,000,000,000)$
• 다음 N개 줄
  • N개의 입국심사대에 대한 심사 소요시간$(T_k)$이 주어짐
  • $(1 \leq T_k \leq 1,000,000,000)$

출력

• M명이 입국심사를 마치는데 걸리는 최소 시간

풀이

각 변수의 범위가 매우 크고, 소요시간의 최솟값을 구하는 문제이므로 이분탐색을 먼저 떠올려 보았다.

소요시간을 'target(mid)'으로 놓고, 해당 target이 가능하다면 더 짧은 소요시간을 탐색해본다. 만약 불가능하다면 더 긴 소요시간에 대해 탐색한다.

	# 해당 소요시간에 끝내는 것이 
	# 가능한 경우
    if is_possible(mid):
        # 가능한 시간 갱신
        answer = mid
        # 더 작은 값에 대해서 탐색
        right = mid - 1
    # 불가능한 경우
    else:
        # 더 큰 값에 대해서 탐색
        left = mid + 1

우선, 심사대 별 소요시간을 담은 배열(t)을 내림차순으로 정렬한다.
그리고 전체 소요시간(target)을 각 심사대의 소요시간(time)로 나눈 몫을 모두 더한다.
그 결과(cnt)가 M보다 크거나 같다면 가능하고, 작으면 불가능하다. 더 작은 target에 대해 탐색하면 되므로 M보다 cnt가 커도 상관없다.
이 과정을 고민하는데 시간을 많이 썼다.

# 소요 시간에 대해 끝내는 것이 가능한지 확인
def is_possible(target):
	cnt = sum(target // x for x in t)
    return cnt >= m

시간복잡도

1. 배열 정렬: $N*logN$
2. 이분탐색
   • 탐색범위: $log(M*T_K)$
   • is_possible: $N$

따라서, 전체 시간복잡도는 $O(N*logM)$
충분히 가능하지만 최악의 경우에는 시간초과가 날 수도 있다.
그리고, 배열을 입력받는 과정이 매우 길기 때문에 input = sys.stdin.readline이 필요하다.

전체 코드

# boj 3079.입국심사
import sys
input = sys.stdin.readline
INF = sys.maxsize

# 입력받기
n, m = tuple(map(int, input().split()))
t = [int(input()) for _ in range(n)]
t.sort(reverse=True)

# 소요 시간에 대해 끝내는 것이 가능한지 확인
def is_possible(target):
    # 해당 소요시간에 심사가능한 인원 수 계산
    cnt = sum(target // time for time in t)
    return cnt >= m

left, right = 0, m * t[-1]
answer = INF
# 소요시간에 대해 이분 탐색
while left <= right:
    mid = (left + right) // 2

    # 해당 소요시간에 끝내는 것이 
    # 가능한 경우
    if is_possible(mid):
        # 가능한 시간 갱신
        answer = mid
        # 더 작은 값에 대해서 탐색
        right = mid - 1
    # 불가능한 경우
    else:
        # 더 큰 값에 대해서 탐색
        left = mid + 1

print(answer)

풀이 git

기타

# 소요 시간에 대해 끝내는 것이 가능한지 확인
def is_possible(target):
    # 해당 소요시간에 심사가능한 인원 수 계산
    cnt = 0
    for time in t:
        cnt += (target // time)
        if cnt >= m:
            return True
    return False

is_possible에서 반복문 중간에 조건을 걸어서 하면 조금 더 빠를 것 같아서 해봤지만, 큰 차이는 없었다. 아주 조금 빨라진 정도...