이분탐색 | BOJ 백준 3079번 입국심사 | Python


created_at : 23 April 2024 - 2 mins read time
Tags: 이분탐색

Table of Contents


BOJ 백준 3079번 입국심사 | Python

📌 백준 3079번 문제 바로가기

🔎 문제 설명

💛 골드 5

- 난이도 ★★★☆
- 이분탐색

이분탐색을 떠올리는 데 조금 시간이 걸렸다. 그리고 각 심사대별로 어떻게 시간을 분배해 계산해줄지 찾는 것이 관건이었다. 이분탐색은 실버까지는 쉽게 풀리나, 골드처럼 조금만 문제를 꼬아도 생각하기 까다로운 문제인 것 같다. 더 연습해야지,,!


📌 문제 풀이 큰 틀은 다음과 같다.

  • 기준점(mid) = 상근이와 친구들이 심사를 받는데 걸리는 총 시간
  • 총 시간을 각 심사대별 시간으로 나누어 검사 가능한 인원 수 ppl를 계산한다.



💻 내 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
T = []
for n in range(N):
    T.append(int(input()))

start, end = min(T), max(T)*M
answer = float('inf')

while start <= end:
    ppl = 0
    mid = (start + end)//2
    
    for t in T:
        ppl += mid // t

    if ppl >= M:
        end = mid - 1
        answer = min(answer, mid)
    else:
        start = mid + 1
    
print(answer)




 

💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).