[Python/파이썬] 백준 14233번 악덕 사장

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

 

코드

n = int(input())
deadlines = list(map(int, input().split()))

deadlines.sort()

l, r = 0, int(1e9)
while l <= r:
    mid = (l+r)//2

    is_possible = True
    for i in range(n):
        if deadlines[i] < mid*(i+1):
            is_possible = False
            break

    if is_possible:
        l = mid+1
    else:
        r = mid-1

print(l-1)

 

조건에 맞는 최댓값을 찾는 문제이기 때문에 매개 변수 탐색(Parametric Search)를 사용하여 풀었다.

 

위 코드는 다음과 같은 과정으로 진행된다:

1. 당연히 마감기한이 짧은 애들부터 먼저 해야 하니까 마감기한을 오름차순 정렬한다.

2. K값을 찾기 위해 매개 변수 탐색을 수행한다. `l <= r`인 동안 아래의 과정을 반복하며 K의 최솟값을 찾는다.

    - mid는 l과 r의 중간값으로 설정한다. mid는 일을 하는 시간 k에 해당하는 값이라고 생각하면 된다.

    - 오름차순으로 정렬된 마감기한들에 대해 i번째 마감기한이 mid*(i+1)보다 작은지 확인한다.

    - 만약 i번째 마감기한이 mid*(i+1)보다 작다면 이 시간(mid=k)은 너무 길다는 뜻이므로 r = mid-1로 조정한다. 그렇지 않다면 l = mid+1로 조정하여 더 긴 시간이 가능한지 알아보러 간다.

3. while 반복문을 다 돌고 난 뒤의 l-1이 최대한 일을 많이 시키면서도 모든 일이 마감기한을 지킬 수 있는 시간이다.