1/31 Coding Test

✅ Coding Test

🎈 3079 입국심사

M명이 N개의 입국심사대를 통과하고자 한다. 그러나 각 입국심사관이 심사를 하는데 소요되는 시간은 사람마다 다르고 k번 심사대에 위치한 심사관이 심사하는데 걸리는 시간은 Tk이다.

최종적으로 M명이 심사를 받는데 걸리는 시간의 최솟값을 구하는 문제.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
array = []
for _ in range(n):
    array.append(int(input()))
array.sort()

start, end = array[0], array[-1]*m
answer = end

while start <= end:
    mid = (start + end) // 2
    total = 0
    for i in range(n):
        total += mid // array[i]
    if total >= m:
        end = mid - 1
        answer = min(answer, mid)
    else:
        start = mid + 1
print(answer)

< 해설 >

로직은 다음과 같다.
1. 입력값 처리 후 정렬하고 start, end 변수를 최단 시간, 최장 시간으로 둔다.
2. while loop를 돌며 start <= end로 조건을 둔다
3. total 변수로써 mid 시간 동안 입국심사를 받는 사람 수를 둔다.
4. for문으로 모든 인원에 대해 total 계산을 하고 M명과 비교를 하며 start, end의 범위를 줄여나간다.

🎈 1561 놀이 공원

N명의 아이들이 한 줄로 서서 1인승 놀이기구를 기다리고 있다. 놀이기구에는 총 M종류의 1인승 놀이기구가 있고 1번부터 M번까지 번호가 매겨져 있다. 만일 여러 기구가 동시에 비어있으면 더 작은 번호가 적힌 놀이 기구를 먼저 탑승한다.
놀이기구가 모두 비어있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램 작성하는 문제

import sys
input = sys.stdin.readline

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

start, end = 0, max(time)*n
total_time = 0 # n명까지 놀이기구 사용 시간
# 주어진 사람 수보다 놀이기구 수가 많으면 0분에 전부 탑승
if n < m:
    print(n)
else:
    # 놀이기구 총 사용 시간 찾기
    while start <= end:
        mid = (start + end) // 2
        person = m
        for i in range(m):
            person += mid // time[i]
        if person >= n:
            end = mid - 1
            total_time = mid
        else:
            start = mid + 1
    # total_time 보다 1분 전에 탑승
    answer = m
    for i in range(m):
        answer += (total_time-1) // time[i]
    # total_time에 탑승한 애들
    for i in range(m):
        if total_time % time[i] == 0:
            answer += 1
        if answer == n:
            print(i+1)
            break

< 해설 >

주어진 N의 범위가 크기에 곧바로 이분 탐색을 활용한 풀이
로직은 다음과 같다.

1. 우선 사람 수보다 놀이기구 수가 더 많으면 사람 수를 출력. (놀이기구 번호와 동일)
2. 이분 탐색으로 사람들이 놀이기구를 모두 타는 시간 찾기
3. 구한 시간 -1분일 때 몇 명까지 탑승가능한지 탐색
4. 앞서 구한 시간 + 1분하면서 탑승하는 사람 수를 계산해 N과 같다면 놀이기구 번호 출력