백준 3079번 : 입국심사

2021. 11. 10. 02:32·알고리즘

https://www.acmicpc.net/problem/3079

 

3079번: 입국심사

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)

www.acmicpc.net

2110번에서 알게된 내용들을 적용해서 생각보다 쉽게 푼 문제다.

 

 M명의 사람들은 입국하기위해 입국심사를 받는다. 심사대는 총 N개가 있고 심사대마다 심사에 소요되는 시간이 정해져있다. M명의 사람들을 모두 통과시키는 최소한의 시간을 구하는 문제이다.

 

 앞서 푼 문제에서 배운 이분 탐색의 요령을 그대로 적용했다. 구하려는 값은 시간이기 때문에 가능한 범위 안에서 조건(시간 안에 사람들이 모두 통과할 수 있는지)을 만족시키는 최소한의 시간을 구한다. 이때 최소화된(최적화된) 시간은 심사시간이 가장 짧은 심사대로 M명의 사람이 모두 통과하는데 걸리는 시간보다 짧거나 같다. 그 범위 안에서 시간을 늘리거나 줄여가며 적절한 시간을 찾을 것이다.

(자료형에 따라 M의 최대가 10억, 심사 시간의 최대가 10억이기 때문에 그냥 10억의 제곱을 끝 범위로 정해도 상관없을 것 같다.)

 

 이제 주어진 시간 안에 최대 몇명이 심사를 통과할 수 있는지 계산해본다. 주어진 시간보다 심사가 오래 걸리는 심사대는 고려할 필요가 없다. 주어진 시간을 한 심사대의 심사시간으로 나눈 몫이 그 심사대에서 시간 안에 통과시킬 수 있는 최대 인원 수이므로, 모든 심사대에서 통과시킬 수 있는 인원의 합과 우리가 통과시켜야 하는 인원(M)과 비교한다. 통과 인원이 적으면 시간이 더 필요한 것이고, 통과 인원이 같거나 많으면 시간을 줄이며 조건을 만족시키는 최소값을 찾는다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
t = sorted([int(input()) for _ in range(n)])
s, e, r = 1, t[0] * k, 0

while s <= e:
    m = (s+e)//2
    cnt = sum([m//i for i in t])

    if cnt >= k:
        e = m-1
        r = m
    else:
        s = m+1
print(r)
저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

백준 1715번 : 카드 정렬하기  (0) 2022.01.12
백준 22871번 : 징검다리(large)  (0) 2021.11.11
백준 2110번 : 공유기 설치  (0) 2021.11.09
백준 17836번 : 공주님을 구해라!  (0) 2021.11.06
백준 13549번 : 숨바꼭질 3  (0) 2021.11.06
'알고리즘' 카테고리의 다른 글
  • 백준 1715번 : 카드 정렬하기
  • 백준 22871번 : 징검다리(large)
  • 백준 2110번 : 공유기 설치
  • 백준 17836번 : 공주님을 구해라!
무슈후슈
무슈후슈
코딩은 창작이다.
  • 무슈후슈
    감성코드
    무슈후슈
  • 전체
    오늘
    어제
    • 분류 전체보기 (123) N
      • 알고리즘 (30)
      • IOS (28) N
      • Swift (4)
      • TIL (41)
      • CS (15)
      • 메모 (2)
      • 시플 (1)
      • RxSwift (2)
  • 블로그 메뉴

    • 홈
    • 태그
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    Realm
    그리디
    비동기
    codable
    프로그래머스
    MVVM
    코딩테스트
    이분 탐색
    http
    그래프 탐색
    백준
    git
    SWIFT
    python
    파이썬
    github
    ios
    다이나믹 프로그래밍
    풀이
    알고리즘
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
무슈후슈
백준 3079번 : 입국심사
상단으로

티스토리툴바