[Python - Binary Search] 3079 입국심사

2022. 9. 13. 23:53· Algorithm/Binary Search
목차
  1. 👨‍🏫 접근
  2. 👨‍🏫 문제 풀이
  3. 📄 전체 코드
  4. 📄 준비
  5. 📄 풀이

📌 문제

상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 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)

📌 출력

첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다. 

📌 문제 풀이

👨‍🏫 접근

처음 문제를 보고 상당히 고민을 하고 있었는데, 막상 풀이가 떠오르니까 거의 3분만에 풀었다. 이 문제에서의 핵심은 m의 범위가 매우 넓다는 것이다. 즉, 이진탐색으로 m을 탐색해야 이 문제의 시간 복잡도를 최소화 할 수 있는 방법이다.

 

m을 탐색하는 것은 해당 시간동안 학생들이 입국 심사를 받는다고 할 때 얼마가 걸리는지 합계를 구하여 m보다 적은지 혹은 많은지에 따라서 탐색의 범위를 바꿔나가는 과정을 거친다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

s = [int(input()) for _ in range(n)]

pl, pr = 1, m * max(s)
ans = 0

while pl <= pr:
    mid = (pl + pr) // 2
    total = sum(map(lambda x: mid // x, s))

    if total >= m:
        pr = mid - 1
        ans = mid
    else:
        pl = mid + 1


print(ans)

📄 준비

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

s = [int(input()) for _ in range(n)]

pl, pr = 1, m * max(s)
ans = 0

pr로는 m과 max(s)를 곱해주었다. 왜냐하면, 입국심사가 최대로 소요되는 시간은 가장 오래 걸리는 심사대에서 모든 인원이 입국 심사를 받는 시간이기 때문이다.

📄 풀이

while pl <= pr:
    mid = (pl + pr) // 2
    total = sum(map(lambda x: mid // x, s))

    if total >= m:
        pr = mid - 1
        ans = mid
    else:
        pl = mid + 1


print(ans)

이제 mid를 구하여 심사 가능한 인원을 체크한다. 각 입국 심사대가 mid라는 시간에 얼마나 심사를 할 수 있는지를 총 합하는 것이다.

 

입력 1에서 심사대가 2개, 인원이 6명, 심사대가 소요되는 시간이 각각 7, 10인 경우를 예로 들자면, 입국 심사가 30이라는 시간이 걸릴 때, 총 심사 가능 인원은 30 // 7 + 30 // 10 = 7이 된다. 즉, 총 심사 시간이 30이면 모든 인원이 심사하고도 1명을 더 심사할 수 있다는 것이다.

 

그래서 만약 total 값이 mid보다 크면 총 심사시간을 더 줄이기 위해서 pr을 mid - 1로 저장한다. 동시에 이 경우가 모든 입국 심사가 가능한 경우이기도 하니 ans에 mid 값을 저장해준다.

📌 총평

코딩테스트는 창의력이 좋아야 하는 것인가...

저작자표시 비영리 (새창열림)

'Algorithm > Binary Search' 카테고리의 다른 글

[Python - Binary Search, BFS] 2585 경비행기  (2) 2022.09.13
[Python - Binary Search] 2110 공유기 설치  (0) 2022.09.04
[Python - Binary Search] 2512 예산  (0) 2022.09.04
[Python - Binary Search] 1654 랜선 자르기  (0) 2022.09.04
[Python - Binary Search] 2805 나무 자르기  (0) 2022.09.04
  1. 👨‍🏫 접근
  2. 👨‍🏫 문제 풀이
  3. 📄 전체 코드
  4. 📄 준비
  5. 📄 풀이
'Algorithm/Binary Search' 카테고리의 다른 글
  • [Python - Binary Search, BFS] 2585 경비행기
  • [Python - Binary Search] 2110 공유기 설치
  • [Python - Binary Search] 2512 예산
  • [Python - Binary Search] 1654 랜선 자르기
턴태
턴태
import { Dream } from "future";
턴태
턴태의 밑바닥부터 시작하는 de-vlog
턴태
전체
오늘
어제
  • ROOT (187)
    • Node.js (37)
      • ES6 (1)
      • TypeScript (3)
      • Express.js (16)
      • NestJS (16)
      • JS (24)
    • 프론트엔드 (29)
      • CS (5)
    • 백엔드 (1)
      • 검색 (2)
      • Database (1)
    • 기타 툴 (1)
      • git (1)
    • 데브옵스 & 인프라 (19)
      • Kubernetes (15)
      • Docker (2)
      • Monitoring (1)
      • IaC (1)
    • Algorithm (90)
      • Implementation & simulation (5)
      • Math (4)
      • Brute Force (1)
      • String (0)
      • Graph (5)
      • Recursion & Backtracking (19)
      • Divide & Conquer (2)
      • Dynamic Programming (18)
      • Greedy (13)
      • Priority Queue (2)
      • Binary Search (6)
      • Data Structure (7)
      • Shortest Path (5)
      • Minimum Spanning Tree (1)
      • Sorting (1)
      • Prefix Sum (1)
    • Linux (1)
      • Ubuntu (1)
    • Diary (5)
      • Algorithm (1)
      • Conference (1)
      • Retrospective (3)
    • Book (0)
      • Self-Development (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Toy Project
  • k8s
  • 함수형 프로그래밍
  • 토이프로젝트
  • 네스트
  • Express
  • 오먹
  • 백트래킹
  • baekjoon
  • TypeScript
  • 노드
  • 인프런X디프만
  • GREEDY
  • 디프만
  • Omuk
  • python
  • 인프런
  • 파이썬
  • 타입스크립트
  • dynamic programming
  • backtracking
  • 쿠버네티스
  • 익스프레스
  • 백준
  • 자바스크립트
  • nestjs
  • N과 M
  • Kubernetes
  • node.js
  • 다이나믹 프로그래밍

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
턴태
[Python - Binary Search] 3079 입국심사
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.