[알고리즘] 백준 파이썬 13702 이상한 술집

📍 문제 탐색하기

프로그래밍 대회 전날, 은상과 친구들은 술집에서 주어진 막걸리 주전자를 최대한 동일한 양으로 나눠 마시려고 한다.
주어진 막걸리를 K명의 사람에게 똑같은 양으로 나눌 때, 최대 용량(ml)을 구하는 것이 목표이다.

---

문제 조건 분석

• 입력 조건
  • 첫 번째 줄:
    • N (막걸리 주전자의 개수, N≤10,000)
    • K (사람의 수, K≤1,000,000 )
  • 두 번째 줄부터: 각 주전자의 용량 (자연수, 최대 2^31 - 1)
• 출력 조건
  • 나눠줄 수 있는 최대 막걸리 용량(ml) 출력

---

가능한 문제 해결 전략

1. 완전 탐색 (Brute Force)
   • 1ml부터 최댓값까지 모든 용량을 시도하는 방법 → 시간 초과 가능성 높음
   • 시간 복잡도: O(K×N)
2. 이분 탐색(Binary Search) 적용 (최적 해법)
   • 가능한 용량 범위를 설정하고 이분 탐색을 통해 최적의 답을 찾음.
   • 시간 복잡도: O(Nlog⁡M), M은 최대 용량.

---

📍 코드 설계하기

알고리즘 아이디어

1. 초기화 단계
   • start = 1 (최소 나눌 수 있는 양은 1ml)
   • end = max(pot) (최대로 나눌 수 있는 양)
2. 이분 탐색 수행
   • mid 값을 기준으로 각 주전자의 막걸리를 mid만큼 나누어 몇 명에게 나눠줄 수 있는지 계산.
   • 조건 분기:
     • cnt >= K: 더 큰 용량이 가능 → start를 증가.
     • cnt < K: 용량을 줄여야 함 → end를 감소.
3. 결과 출력
   • 최종적으로 최대 용량을 출력.

---

📍 시도회차 및 수정 사항

import sys
input = sys.stdin.readline

# 입력 받기
N, K = map(int, input().split())

# 주전자 용량 입력
pot = []
for _ in range(N):
    pot.append(int(input()))
    
# 이분 탐색 초기 범위 설정
start = 1  
end = max(pot)

result = 0

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

    cnt = 0  # 현재 mid 용량으로 몇 명에게 나눌 수 있는지 계산
    for i in range(N):
        cnt += pot[i] // mid  # mid 용량으로 나눈 몫을 더함

    if cnt >= K:  # K명 이상 나눠줄 수 있으면, 용량을 늘려보기
        result = mid
        start = mid + 1
    else:  # K명보다 적게 나눠질 경우, 용량을 줄여야 함
        end = mid - 1

print(result)

---