[Gold V] 입국심사 - 3079
성능 요약
메모리: 39268 KB, 시간: 1000 ms
분류
이분 탐색, 매개 변수 탐색
문제 설명
상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 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)
출력
첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다.
풀이
아이디어
- 최적화 문제를 결정문제로 바꾼다 라는 가장 기초적인 개념에서부터 아이디어를 구상하였다.
start는 0으로,end는 모든 사람이 가장 오래걸리는 창구로 가는 두고 풀기로 결정하였다.- 이분탐색을 진행하여
mid를 모든 리스트 요소들로 나눈뒤 그 합을 구해mid시간동안 창구를 이용할 수 있는 사람의 수를 구한다. - 만약 매개 변수 탐색에서 사람의 수가
m보다 많거나 같으면end를 줄이고 그 반대라면start를 올린다.
코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
lst = [int(input())for _ in range(n)]
lst.sort()
start, end = 0, max(lst)*m
result = end
while start <= end:
mid = (start + end) // 2
if (sum(list(map(lambda x: mid // x, lst)))) >= m:
end = mid - 1
result = min(result, mid)
else:
start = mid + 1
print(result)회고
아이디어 내기가 나에겐 너무 어려웠던 문제,,
우선 걸리는 시간을 기준으로 탐색을 해야겠다! 라고까지만 생각이 나고, 그 이후로 어떤 방식으로 탐색 조건을 좁혀나갈것인가에서 막혔다.
힌트를 보고 풀이를 하니 코드 구현에는 매우 금방 끝났다.
이분 탐색 문제를 여러가지 풀이하니까 구현은 괜찮은데 아이디어 내기가 너무 까다로웠고, 사고력을 조금 더 키워야 한다는 생각이 들었다.
풀이하면서 든 생각인데, 과연 내가 이 문제를 알고리즘 분류 없이 보고 푼다고 하면 이분탐색이라는 것을 쉽게 떠올릴 수 있을까 라는 의문도 들었는데, 일단 몸빵으로 무작정 많이 풀다보면 되지 않을까 라는 생각으로 지금은 일단 생각을 비우고 풀기에만 집중하기로 했다.
