[백준] 1561번 - 놀이 공원 / 골드 2 / 파이썬 풀이

문제 링크

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

1561번: 놀이 공원

 

시간 제한 : 2초

메모리 제한 : 128 MB

 

문제 요약

• N명의 아이들이 한 줄로 줄을 서서 놀이공원의 1인승 놀이기구를 기다리고 있다. (N은 입력으로 주어짐)
• M 종류의 1인승 놀이기구들이 있으며, 놀이기구에는 1번부터 M번까지 번호가 매겨져 있다. (M은 입력으로 주어짐)
• 각 놀이기구들은 운행 시간이 정해져 있으며, 놀이기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 여러 놀이기구가 동시에 비어 있을 경우, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탄다.
  
  
• 문제 : 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하시오.
  

 

입력

예지 입력 1

3 5
7 8 9 7 8

예제 입력 2

7 2
3 2

예제 입력 3

22 5
1 2 3 4 5

 

출력

예제 출력 1

3

예제 출력 2

2

예제 출력 3

4

---

풀이

"남은 사람의 수(놀이기구를 타야 하는 사람 수)를 이분탐색으로 최대한 줄여보자!"

import sys


# afterPlay : 배열 a가 주어질 때 0부터 t분까지 놀이기구를 탄 사람(다 탄 사람)의 수를 리턴하는 함수
def afterPlay(a, t) -> int:
    played_people = 0
    for i in a:
        played_people += t // i     # t분일 때 놀이기구를 타고 있는 중인 사람은 카운트하지 않음.
    return played_people


# Binary_Search : 이분 탐색을 통해 정확히 주어진 n명의 사람만 처리하는 시간을 answer에 갱신하는 함수
def Binary_Search(left, right):
    global answer
    while left <= right:
        mid = (left + right) // 2       # 이분 탐색 위한 중간값 정의.
        res = afterPlay(playtime, mid)  # res : mid 분일 때 놀이기구 타는 것을 완료한 사람의 수
        if res >= n - m:        # mid 분일 때의 처리한 사람의 수가 남은 사람 수 이상일 때
            right = mid - 1     # 이분탐색에서의 탐색최댓값을 1(분) 줄인다.
            answer = mid        #
        else:           # mid 분일 때의 처리한 사람의 수가 남은 사람 수보다 적을 때
            left = mid + 1      # 이분탐색에서의 탐색최솟값을 1(분) 늘린다.


# adjust : a분인 순간에 남는 놀이기구 중 n번째 인덱스(놀이기구)를 리턴하는 함수
def adjust(a, n):
    th = []
    for idx, p_time in enumerate(playtime):
        if a % p_time == 0:     # 현재 남은 시간(분)이 놀이기구 운행시간의 배수가 된다면
            # (운행 시간이 a의 약수가 되어야 하므로 a분 순간에 놀이기구가 놀려지고(?) 있을 것이므로)
            th.append(idx)
    return th[n - 1] + 1


n,m = map(int, sys.stdin.readline().split())    # 입력받음 - N명의 아이들, M개 종류의 놀이기구
playtime = list(map(int, sys.stdin.readline().split()))     # 각 놀이기구들의 운행시간(소요되는 시간)


if n <= m:      # 줄을 선 아이들의 수가 놀이기구 종류보다 적다면.
    print(n)    # 줄의 마지막에 선 아이는 n번째 놀이기구를 타게 된다.    (작은 번호의 놀이기구부터 탑승한다고 하였으므로)
else:
    answer = 0
    # ans 갱신
    # 여기서 left를 1, right를 문제의 최대 입력으로 하지 않은 이유는 실제 끝나는 시점이
    # 문제의 최대 입력(20억)보다 클 때가 존재하기 때문
    Binary_Search(min(playtime), max(playtime) * n)
    # k : answer 분의 순간에 탈 사람의 수
    k = n - m - afterPlay(playtime, answer - 1)
    # 정답 출력
    print(adjust(answer, k))

 

참고

https://peisea0830.tistory.com/54

[Python 3] BOJ - 1561 "놀이 공원"