[Baekjoon Online Judge] 백준 3079번 입국심사(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 3079번 입국심사

(Python)

(글쓴날 : 2020.04.07)

 

---

* Baekjoon Online Judge, 백준 3079번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 3079번 입국심사

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/3079

3079번: 입국심사

---

2) 풀이 과정

입국 심사대의 개수 N과, 심사를 받을 인원 M이 주어지고, 각 입국 심사대의 심사에 걸리는 시간이 주어질 때 모든 인원이 심사를 받는 최소 시간을 구하는 문제입니다.

 

저의 경우, 이분 탐색의 파라메트릭 서치를 적용했고, 중간값을 최소 시간으로 설정하여 탐색해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
N, M = map(int, input().split())
time = [int(input()) for _ in range(N)]
result = 0
left = 0
right = M * max(time)
 
while left <= right:
    mid = (left + right) // 2
 
    judgedPeople = 0
    for t in time:
        judgedPeople += mid // t
    
    if judgedPeople < M:
        left = mid + 1
    else:
        result = mid
        right = mid - 1
 
print(result)

---