[백준 1561] 놀이 공원 - Python

문제 보기

[사용한 알고리즘]

이분 탐색(binary search)

 

[문제 접근]

N명의 아이들을 놀이기구에 태울 수 있는 시간을 구한 후 놀이기구의 번호를 구하였습니다. N의 범위가 크기 때문에 0초부터 시간을 탐색하는 것이 아니라 이분 탐색으로 시간을 구하였습니다. 

 

[알고리즘]

1. 놀이기구의 수보다 아이들의 수가 적으면 아이들의 수를 출력합니다.

2. 이분 탐색을 통해 아이들을 모두 태울 수 있는 시간을 찾습니다.

3. 구한 시간 - 1분까지 몇 명의 아이를 태울 수 있는지 탐색합니다.

4. 구한 시간에 탑승하는 아이들을 계산하면서 제일 마지막에 탑승하는 놀이기구의 번호를 출력합니다. (놀이기구 탑승 인원이 N명이 될 때의 놀이기구 번호를 출력하면 됩니다)

 

[코드]

import sys

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:
        # 이분 탐색
        left, right = 0, 60000000000
        t = None
        while left <= right:
            mid = (left + right) // 2
            cnt = m
            for i in range(m):
                cnt += mid // t_list[i]
            if cnt >= n:  # n명을 태울 수 있는 상황
                t = mid
                right = mid - 1
            else:
                left = mid + 1

        # 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:  # t 시간에 탑승한 아이
                cnt += 1
            if cnt == n:
                print(i + 1)
                break