[BOJ 3079] 입국심사

짱J·2023년 2월 9일

백준 파이썬

알고리즘 문제 풀이

목록 보기

16/30

문제 설명

예제 1에서는

1번째 심사대에서 4명
2번째 심사대에서는 2명을 검사하면

28초만에 6명 모두 입국심사를 할 수 있고, 이 때가 최소이다.

예제 2에서는

1번째 심사대에서 2명
2번째 심사대에서는 1명
3번째 심사대에서는 1명
4번째 심사대에서는 1명
5번째 심사대에서는 0명
6번째 심사대에서는 4명
7번째 심사대에서는 1명

8초만에 10명 모두 입국심사를 할 수 있고, 이 때가 최소이다.

구현 아이디어

이분 탐색 알고리즘을 사용할 때 중요한 것은 정답에서 요구하는 값을 변수로 하여 이분 탐색을 진행하는 것이다.
지금 문제에서 요구하는 것은 심사를 받는데 걸리는 총 시간의 최솟값이므로 이것을 변수로 해야 한다.

심사를 받는데 걸리는 총 시간을 mid로 한다.

mid동안 몇 명을 입국 심사할 수 있을지 계산한다.

각 심사대에서 최대로 심사할 수 있는 사람의 수를 구하고, 이 합을 mx라는 변수에 담는다.

mx가 m보다 크면, end를 mid로 한다 (= 다 검사하고도 시간이 남음, mid를 줄어야 함)

mx가 m보다 작으면, start를 mid로 한다 (= 해당 시간 안에 모두를 검사하지 못함, mid를 늘려야 함)

(사진)

이 때 start = 1, end = m * arr[-1]로 초기화한다.
- end는 모든 사람이 제일 오래 걸리는 심사대에서 심사를 했을 때를 의미한다.

전체 코드 1 - 틀렸습니다

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

arr = []
for _ in range(n):
    arr.append(int(input()))

# 이분 탐색의 기본은 정렬
arr.sort()

start = 1
end = m * arr[-1] # 모든 사람이 제일 오래 걸리는 심사대에서 심사를 했을 때
mx = 0

while start <= end:
    temp = []
    mid = (start + end) // 2
    if start == mid:
        start += 1
        continue
	
    # mid동안 몇 명을 심사할 수 있을지 계산
    for elem in arr:
        temp.append(mid // elem)
    
    mx = sum(temp)

    if mx == m:
        break
    
    if mx > m:
        end = mid
    else:
        start = mid

print(mid)

전체 코드 2 - 맞았습니다

틀린 원인 ❓

반례와 테스트 케이스를 모아둔 글을 참고하여 입력이

12 13
8
27
6
3
10
5
11
14
21
19
12
8
정답: 12

일 때 13이 나와 틀리는 것을 알 수 있었다.

이것은

if mx == m:
        break

를 사용하여 우리가 구한 시간 내에 M명을 모두 심사할 수 있으면 탐색을 종료하기 때문에 틀린 것이다.
우리는 최소 시간을 구해야 하기 때문에 조건을 충족하는 값을 구했어도 더 작은 값이 없는지 한 번 더 확인해주어야 한다.

정답 코드 ‼️

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

arr = []
for _ in range(n):
    arr.append(int(input()))

arr.sort()

start = 1
end = m * arr[-1]
mx = 0

while start <= end:
    temp = []
    mid = (start + end) // 2
    if start == mid:
        start += 1
        continue

    for elem in arr:
        temp.append(mid // elem)
    
    mx = sum(temp)

	# mx > m을 mx >= m으로 변경해주었다
    if mx >= m:
        end = mid
    else:
        start = mid

print(mid)