3079번
-
[백준] 3079번 입국 심사알고리즘/백준 2021. 8. 27. 18:44
문제 링크 프로그래머스 풀이 심사대의 범위가 1 ~ 100,000이고 친구들의 숫자가 최대 10억명이므로 이분 탐색을 사용하지 않으면 시간이 너무 오래 걸리게 될 겁니다. 이 문제에서는 어디에 이분 탐색을 사용해야 할까요. 우리가 구하고자 하는 답은 주어진 인원이 입국 심사 하는 데 걸리는 최소 값입니다. 입국 시간과 인원과의 상관 관계를 먼저 생각해볼게요. 예제에서 두 개의 심사대가 주어지고 각각 심사 시간이 7분, 10분입니다. 만약 입국자에게 5분이 주어진다면 어느 누구도 심사대를 통과할 수 없을 겁니다. 7분이면 1명만 통과할 수 있고요 10분은 돼야 2명이 받을 수 있습니다. 직관적으로 계산할 수 있지만 수식으로 해보면, 주어진 시간이 X일 때 각 심사대의 심사 시간을 나눈 값을 더한 총합입니다..