[알고리즘] 백준 3079 Python

 

분류

파라매트릭 서치

혼자 힘으로 해결 했는가?

애매하다..

느낀 점

이런 류의 문제가 생각보다 나는 접근이 힘들다.

문제의 요구사항을 그대로 수행하는 방식으론 절대 해결이 불가능 하다.

일단 입력 값 부터 10억이기 때문에 무조건 log로 만들어야 하고 이는 이분 탐색이 필요함을 알 수 있다.

 

그러나 어디에 이분 탐색을 써야하는지가 생각하기 힘들다.

 

우선 이 문제는 약간의 그리디로 접근을 해야하는데

그렇다고 무조건 그리디로 해결하면 안된다.

 

2가지이면 특정 사람이 1번에서 검사를 받거나 or 2번에서 검사를 받는 형태의 dp로 접근을 하겠지만

(그러나 입력 값이 10억이라 그냥 안됨)

우선 어떻게 해결을 할지부터가 어려웠다.

 

이 문제는 어렵게 생각하기 보다는 그냥 가장 오래 걸리는 시간까지 1씩 증가 시키면서

모두가 검사를 완료하는지 체크하고 그러다 보면 가장 작은 값을 찾게 되는데 이 값이 정답이다.

 

단, 검사를 완료하는지 검사하는 부분에서 그리디로 시간이 적게 걸리는 심사대에 친구가 최대한 많이 갔다!

이렇게 검사를 해야하기 때문에 그리디도 있다고 생각이 든다.

 

여기까지 왔으면 이제 1부터 증가시키는 브루트 포스에서 이분 탐색으로 쉽게 전환이 가능하다.

 

1부터 쭉 늘려가는 것이 아니라, 이분 탐색을 통해서 찾으며 이분 탐색 동안 찾아진 시간을 

가장 작은 시간과 계속 갱신하면 된다.

 

즉 파라매트릭 서치를 사용하게 된다.

 

나무 자르기, 랜선 자르기와 같은 문제랑 결국 접근 법이 같지만.... 뭔가 연막이 깔려 있는 느낌....

---

 

내가 작성한 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
time = []
for _ in range(N):
    time.append(int(input()))

left = min(time)
right = max(time) * K
result = float('inf')

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

    for i in time:
        total += mid // i

    if total >= K:
        right = mid - 1
        result = min(result, mid)

    else:
        left = mid + 1
print(result)

 

 

 

---

비슷한 문제들