[ 백준 3079 해설 ] ( python ) 입국심사

 

📚 입국심사

 

 

문제

상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 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 복사

2 6
7
10

예제 출력 1 복사

28

예제 입력 2 복사

7 10
3
8
3
6
9
2
4

예제 출력 2 복사

8

 

 

 

 

✍ 접근

• dp를 이용해서.. 시간이 지날 때마다 남는곳을 간다/안간다로 표기해서... 구해줄까!?!?를 생각했지만
• (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)
• 이걸보고 포기
• 이분탐색으로 풀어야 하는 문제다.

 

 

 

 

 

정답코드 

# ✨ 입력
import sys
input = sys.stdin.readline
N,M = map(int,input().split()) # 심사대, 상근이와 친구들

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

# ✨ 이분탐색
lt = 0 
rt = min(arr) * M # 최소값으로만 다 갔을 때 걸리는 시간
res = 0

while lt <=rt:
    mid = (lt+rt) // 2
    cnt = 0
    for x in arr:
        cnt += mid // x

    if cnt >= M:
        rt = mid-1
        res = mid
    else:
        lt = mid +1
print(res)

해설

입력

• 문제에서 나온 값을 입력받는다
• 이분탐색 : 일단 정렬하기. sorted를 이용해서 arr을 정렬해준다.

이분탐색

• lt를 0으로
• rt를 min(arr)*M 으로 설정해준다.
• 여기서 주의해야 할 점이, 이 lt와 rt는 배열 내를 가리키는 pointer이라기보다는 걸릴 수 있는 시간의 끝과 끝을 나타내는 용도로 쓰였다 ==> 뭔가 3차원적인 생각인듯
• while문을 돌면서
  • mid = (가장 적게 걸리는 시간 + 가장 오래 걸릴 수 있는 시간) //2 == 중간정도 시간
    을 설정해주고
  • 그 시간 안에 몇 명의 사람이 통과할 수 있는지 센다
    • 심사대마다 걸리는 시간을 돌면서 
      가장 적은 심사대부터 greedy를 이용해서 통과할 수 있는 사람의 수를 세어준다.
    • 만약 통과할 수 있는 최대 사람이 상근이와 친구들 이상의 수라면 
      rt = mid -1을 해주고
      res를 mid로 변경해준다 
    • else
      lt = mid + 1로 변경해준다

 

 

⭐ 배움

• 이분탐색을 3차원적으로 생각하기
• 이분탐색 하나로 정말 다양한 문제를 출제할 수 있다는 것을 깨달았다