[Python] BOJ 1561 - 놀이공원

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

1561번: 놀이 공원

# N이 20억이고 M이 1000이므로 이분탐색을 사용해야 한다는 것을 알 수 있다.

   이분탐색을 사용하는 문제는 '이분탐색' 자체로 후보수를 매우 극단적으로 줄일 수 있기 때문에

   풀이 자체는 naive한 경우가 많았다. 특히 매개변수 탐색 문제를 여러개 풀어보면서 느꼈다.

   이 문제 역시 이분탐색이란 걸 생각한 뒤, naive한 방법을 생각했는데 그게 맞았다.

 

 

1. M이 1이면 놀이기구가 하나이므로 그냥 1을 출력해준다. 1이 아닌 경우 매개변수 탐색을 통해 답을 찾아준다.

   lo = 1, hi = 600억으로 설정해준다. (N의 최대가 20억이고 놀이기구 시간의 최댓값이 30이기 때문이다.)

   이분 탐색을 통해 mid값을 찾아준 뒤 check(mid)가 True이면 hi = mid, False이면 lo = mid + 1을 해준다.

 

2. 최종적으로 마지막 아이가 타게 되는 시간이 lo에 들어가 있을 것이다.

   그런데, 우리가 구하는 것은 마지막 아이가 타게 되는 시간이 아니라 그 아이가 타는 놀이기구 번호이다.

   따라서 작업을 한단계 더 해줘야 한다.

 

3. 처음에 people에 M을 넣어준다. (1초에 모든 인원이 놀이기구에 다 타기 때문에)

    people에 "(lo - 1) // 놀이기구의 작동시간" 을 더해준다.  (lo - 1초까지 놀이기구에 탑승한 인원)

 

4. 그리고 마지막 lo초가 되었을 때 상황을 살펴보자.

    앞의 놀이기구부터 lo로 나눈 나머지가 0이면 people + 1해준다. 그리고 people이 N이 되었을 때

    마지막 아이가 그 놀이기구를 탄 것이므로 i+1을 출력해주고 break해준다. (i가 0부터 시작하기 때문)

 

# check함수: mid를 매개변수로 넘겨받아 cnt가 N이상인지 판단해준다.

                   처음에 cnt = M을 해준다. (1초에 M명이 놀이기구를 다 탔으므로)

                   "cnt += mid // 놀이기구 작동시간"을 해준다.

                   최종적으로 cnt >= N이면 True를 리턴해주고 아니면 False를 return해준다.

 

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
rides = list(map(int,input().split()))

def check(m):
    cnt = M
    for r in rides:
        cnt += m // r
    return cnt >= N

if M == 1:
    print(1)
else:
    lo, hi = 1, 60000000000
    while lo != hi:
        mid = (lo + hi) >> 1
        if check(mid):
            hi = mid
        else:
            lo = mid + 1

    if lo == 1:
        print(N)
    else:
        people = M
        for r in rides:
            people += (lo - 1) // r
        
        for i in range(M):
            if lo % rides[i] == 0:
                people += 1
            if people == N:
                print(i + 1)
                break

(solved.ac 티어: 골드 2)

 

# 뭔가 이제 풀 문제들 찾기가 귀찮아서 예전에 틀리고 못풀었던 문제들을 풀고 있다.

   2년 전 이분탐색이 뭔지도 모를때 이 문제에 내가 짠 코드를 보면 아주 귀엽다 ㅋㅋㅋㅋ

   또, 확실히 실력이 많이 늘었다는 것도 느껴진다