[BOJ] [Python] 3079번 : 입국심사

이진탐색을 이용하여 풀었다.

 

 

이 문제의 난관은 'mid값의 중복' 이었다.

 

n = 5, times = [2, 4, 8]

 

 

만약 mid가 8이라면, T(k) = 2, 4, 8 모두 8초까지 작업을 수행할 수 있다.

하지만 이 예제의 인원은 5명으로 제한되어 있기 때문에 T(k) = 2만 8초까지 수행한다.

 

이를 어떻게 해결해야 할까?

 

'입국 심사를 통과해야 하는 인원[입력값] == 입국 심사를 통과할 예상 인원'이 아니라,

'입국 심사를 통과해야 하는 인원[입력값] <= 입국 심사를 통과할 예상 인원'이라고 생각하면 된다.

 

즉, 최솟값을 구하면 된다.

 

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

i_n = num[0] # 심사원 수
i_m = num[1] # 친구 수

i_t = [] # 심사원 시간

for i in range(i_n):
    i_t.append(int(input()))

i_t.sort()

def cal(li, target):
    count = 0

    for l in li:
        count += target // l

    return count

def BSearch(li_t, fri_num):
    low = li_t[0]  # mid가 작을수록 인원이 적어진다.
    high = li_t[0] * fri_num # mid가 클수록 인원이 많아진다.

    while(low <= high):
        mid = (low + high) // 2
        new_fri_num = cal(li_t, mid)

        if(fri_num <= new_fri_num):
            reuslt = mid
            high = mid - 1

        else:
            low = mid + 1

    return reuslt


print(BSearch(i_t, i_m))

 

 

'pypy'로 제출하지 않으면 시간초과가 발생한다.

 

차차 해결해보자~ 

 

아무래도 함수 호출 자체에 시간이 은근 걸리는 듯 하다.

함수를 없애고 함수 기능 부분을 그냥 삽입하더니, 시간초과가 발생하지 않는다.

 

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

i_n = num[0] # 심사원 수
i_m = num[1] # 친구 수

i_t = [] # 심사원 시간

for i in range(i_n):
    i_t.append(int(input()))

i_t.sort()


def BSearch(li_t, fri_num):
    low = 1 # mid가 작을수록 인원이 적어진다.
    high = li_t[0] * fri_num # mid가 클수록 인원이 많아진다.

    while(low <= high):
        mid = (low + high) // 2

        new_fri_num = 0

        for l in li_t:
            new_fri_num += mid // l

        if(fri_num <= new_fri_num):
            reuslt = mid
            high = mid - 1

        else:
            low = mid + 1

    return reuslt


print(BSearch(i_t, i_m))