BeakJoon 1561. 놀이 공원 - 이분 탐색으로 마지막 아이 찾기

조건을 만족하는 최소시간을 구하고, 최소시간-1초에 몇명이 탈 수 있는지 확인하여 최소시간이 되었을 때 태워야하는 인원수와 놀이기구 번호를 찾는다.

문제 URL: https://www.acmicpc.net/problem/1561

😒문제

---

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

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

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

👀제약조건

---

입력

첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.

출력

첫째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력한다.

예제 입력 1

3 5
7 8 9 7 8

예제 출력 1

3

예제 입력 2

7 2
3 2

예제 출력 2

2

예제 입력 3

22 5
1 2 3 4 5

예제 출력 3

4

🤩접근방법

---

이분탐색 문제유형입니다.

문제는 N명의 학생을 M개의 놀이기구에 태워야 한다. → 언제가 최소일까? → 최소시간을 활용해서 가장 마지막으로 타는 학생이 누구일까? → 그 학생이 탄 놀이기구 번호는 무엇일까? 순으로 찾아가야합니다.

이 문제에서 N명이 놀이기구를 타는데 걸리는 가장 긴 시간은 가장 긴 놀이기구 운행시간 * N입니다.

N의 범위가 2,000,000,000으로 아주 큰 숫자이기 때문에 N명을 태울 수 있는 시간을 구하기 위해서는 이분탐색으로 접근해야합니다.

1. 놀이기구 M개가 N명보다 같거나 많으면 0초에 모두 탈 수 있기 때문에 N번째 학생은 N번째 놀이기구에 타면 됩니다.

2. 놀이기구 M개보다 N명 더 많다면, N명이 M개의 놀이기구를 탈수 있는 최소 시간을 구해야합니다.

   이 최소시간을 구하는 이유는 최소시간에 M명을 태울 수 있다는 의미는 최소시간-1초엔 M명보다 더 적은 학생이 타고 있다는 의미입니다.

   즉, 최소시간-1 초에는 몇 명이 타고있는지 확인 후 입력값으로 주어진 학생수 N과 비교하면 딱 최소시간 이 되었을 때 몇 명의 학생이 놀이기구에 타야하는지 알 수 있습니다.

3. 예로 7명의 학생이 있다고 하겠습니다.

   이분탐색으로 학생 모두 놀이기구를 탈 수 있는 최소시간 6초를 찾고, 5초에서 5명을 태우고 있다면 6초에 2명이 타야합니다. 이제 낮은 번호의 놀이기구부터 확인하면서 놀이기구 운행시간을 6초로 나누었을 때 나머지가 0인지 확인하여 놀이기구가 6초에 사람을 태울 수 있는지 확인합니다.

   사람을 태울 수 있는 2번째 놀이기구를 찾았다면, 해당 놀이기구의 번호를 출력합니다.

🤔풀이

---

N, M = map(int,input().split())
seq = list(map(int,input().split()))

left = 0
right = (max(seq)*N)+1

def find_last_persion(time):
    #마지막 시간의 1초 전 몇 명 탈 수 있었는지?
    before_end = time - 1

    t = 0
    for s in seq:
        t += (before_end // s + 1)

    #최소시간 time 시간에 타야하는 인원 수 
    diff = N - t
        
    last = 1
    while diff:
        for i in range(len(seq)):
            if  time % seq[i] == 0:
                last = i+1
                diff -= 1
                if diff == 0:
                    break
    return last
    
def check(time):

    #time이란 시간동안 각 놀이기구에 탈 수 있는 사람의 합을 구해서
    #M보다 크면 모든 아이들이 해당 시간안에 놀이기구를 탈 수 있음 
    t = 0
    for s in seq:
        t += (time // s) + 1
    
    if t >= N:
        return True
    else:
        return False
    
if N <= M:
    print(N)

else:
    while left + 1 < right:
        mid = left + (right - left) // 2

        if check(mid):
            right = mid
        else:
            left = mid
        
    #최소 시간(right)에서 마지막에 타는 사람이 탈 놀이기구는 몇 번째 놀이기구?
    print(find_last_persion(right))

🧐

---

0초부터 놀이기구를 탈 수 있기 때문에 (최소시간 // 놀이기구 운행시간) 을 구하고 +1을 해줘야합니다.

for s in seq:
        t += (time // s) + 1

최소시간-1일 때도 마찬가지로 0초일때 태울 수 있는 학생들을 카운팅해주기 위해 +1을 포함해 계산해야합니다.