[BOJ][python] 1561 놀이공원

조건을 binary search로 찾아 놓은 후에 계산하기  

 

문제

N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.

모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.

놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.

 

나의 풀이

시간을 1분씩 늘려가며 몇명의 아이들이 탈 수 있는지 카운트해가면서 문제를 해결할 수 있습니다.
그러나 문제가 요구하는 시간을 맞추기 위해서는 더 빠른 방법이 필요합니다.
시간 t가 주어지면 놀이기구를 탄 아이들의 수를 계산할 수 있습니다.
n 번째 아이가 놀이기구를 타기위해 필요한 시간을 빠르게 구한다면 다음과 같이 log(n) 혹은 m 의 시간으로 문제를 해결할 수 있습니다.

import sys

def get_time(n:int,m:int,t_list:list) -> int:
    # 이분 탐색
    left, right = 0, n * max(t_list)
    t = None
    while left <= right:
        mid = (left + right) // 2
        cnt = m # 초기 m 명 태우고 시작
        # mid 분 동안 몇 명 태울 수 있는지 계산하기 
        for i in range(m):
            cnt += mid // t_list[i]
        if cnt >= n: # n명을 태울 수 있는 시간 기록하고 더 짧은 시간 없는지 찾아보기
            t = mid
            right = mid - 1
        else: # n명을 태우기 위해서는 시간이 더 필요
            left = mid + 1
    return t


if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().split())
    t_list = list(map(int, sys.stdin.readline().split()))

    if n < m:
        print(n)
    else:
        t = get_time(n, m, t_list)
        # t - 1에 탑승한 아이들의 숫자를 계산합니다.
        cnt = m
        for i in range(m):
            cnt += (t - 1) // t_list[i]
        # t분에 탑승할 수 있는 놀이기구를 앞에서부터 확인한다.
        for i in range(m):
            if t % t_list[i] == 0:  # 탈 수 있는 놀이기구 발견
                cnt += 1
            # 탑승한 아이가 n 명이 되었을 때 종료합니다. 
            if cnt == n:
                print(i + 1)
                break