[Python/코테] 백준 13702 이상한 술집

13702 이상한 술집

문제 및 조건 설명: https://www.acmicpc.net/problem/13702

알고리즘 설계

💡idea.

기준 용량을 찾아야 한다.

막걸리의 최대 용량이 2^31 -1로 범위가 크므로, 이분탐색을 이용해서 빠르게 적절한 용량을 찾아낼 수 있다.

 

🎲step.

이진 탐색을 진행해서 기준 용량을 찾아낸다.

 

알고리즘 구현

import sys

n, k = map(int, input().split())
arr = [int(sys.stdin.readline()) for _ in range(n)]

start = 1
end = max(arr)

result = 0

while (start <= end):
    total = 0
    mid = (start + end) // 2

    for i in arr:
        if i >= mid:
            total += i // mid

    if total < k:
        end = mid - 1       # 새로운 값으로 다시 계산
    else:
        result = mid      # 가능한 값 저장
        start = mid + 1  # 더 큰 값으로도 가능한지 확인

print(result)

* 참고로, start = 0 으로 초기값을 두면 런타임 에러(ZeroDivisionError)가 발생한다. 막걸리의 용량은 0ml가 될 수 없기 때문 ~ !

나다어

• 출력해야 하는 값이 무엇인지 확인하면 의외로 코드를 어떻게 구성해야 하는지 감을 잡을 수 있다!
• 이진 탐색의 가장 기본적인 유형이다 (파라메트릭 서치). 아래 포스팅의 1번 예제 - 떡볶이 떡 만들기와 답안이 거의 동일하다.

2023.05.01 - [Algorithm] - [Python/코테] 이진 탐색 (Binary Search)

[Python/코테] 이진 탐색 (Binary Search)