Coding 공부

import sys
import math
def input():
    return sys.stdin.readline().rstrip()
def check(mid):
    cnt = 0
    for time in arr:
        temp = math.ceil(mid/time)
        cnt += temp
    return cnt

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

arr = list(map(int,input().split()))


left = 0
right = (N//M+1)*30+1

result = 0
while left+1<right:
    mid = (left+right)//2
    if check(mid)>=N:
        right = mid
    else:
        left = mid

result = 0
prev_person = check(right-1)
remain_cnt = N - prev_person
for i in range(M):
    temp = math.ceil(right/arr[i]) - math.ceil((right-1)/arr[i])
    if temp>0:
        remain_cnt -= temp
        if not remain_cnt:
            result = i
print(result+1)

 이분탐색을 활용한 문제이다. 이 문제를 푸는 방법은 다음과 같다.

모든 인원이 탈수 잇는 시간을 구하고, 그 시간을 가지고 마지막 탑승할 놀이기구를 찾는것이다. 

먼저 모든인원이 탈수 있는 시간을 이분탐색으로 먼저 찾는 것이다.

이분탐색으로 특정시간을 구하고, 그 특정시간에 놀이기구에 탑승할 수 있는 인원을 구한다.

그리고 인원이 전부 탈수 있는 최소한의 시간을 구하면 되는 것이다.

그러면 우리가 구한 right는 N명의 어린아이들을 모두 태울수 있는 시간인것이다.

그러면 right-1은 N명의 어린아이를 태우지 못하는 직전의 시간이다.

그래서 우리는 전체 N명에서 right-1에서 태울수 있는 어린아이의 수를 구하고,

남은 수를 가지고 마지막 아이가 탈 놀이기구의 번호를 찾을 수 있다.

찾는 방법은 현재 시간에서 직전시간의 인원을 빼서 0이 아니라면 right라는 시간에서 인원이 탑승을 하게 된것이다.

그 점을 이용해서 하나씩 빼가면서 remain_cnt가 0이 되었을때의 값을 구하면 된다.

import sys

def input():
    return sys.stdin.readline().rstrip()

def check(mid):
    if mid<0:return 0
    cnt = 0
    for t in range(1,31):
        cnt += (mid//t*time_list[t])
    return cnt + M
N,M = map(int,input().split())

time_list = [0 for _ in range(31)]
arr = list(map(int,input().split()))
for t in arr:
    time_list[t] += 1
left = -1
right = (N//M+1)*30+1

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

    if check(mid)>=N:
        right = mid
    else:
        left = mid


remain_cnt = N - check(right-1)
for i in range(M):
    if not right%arr[i]:
        remain_cnt -= 1
        if not remain_cnt:
            print(i+1)
            break

위 풀이는 동일한데 math.ceil을 쓰지않는 풀이이다.

최초 0초에 탑승하는걸 별도로 M으로 빼주고 그 이후의 시간대에서 탑승한 것을 세준 것이다.

풀이 방법 자체는 동일하다.