[TIL] 백준 13702 - 이상한 술집 ( python )

📌 문제 탐색하기

N : 막걸리 주전자 개수 ( 1 ≤ N ≤ 10,000)

K : 친구 수 ( N ≤ K ≤ 1,000,000 )

막걸리 용량 : 0 ≤ 용량 ≤ 2³¹ - 1

 

K명의 사람에게 각 주전자의 막걸리를 섞지 않고 동일한 용량(x ml)씩 나눠주려고 할 때,
가능한 용량(x)의 최댓값을 구하는 것이 핵심입니다.

가능한 시간복잡도

1. 이분탐색
   
   • 각 주전자마다 serving 가능한 개수를 계산 → O(N)
   • 가능한 용량(x)의 범위는 1부터 max(rice_wines) (최대 약 2³¹)까지 → 대략 O(log(max(rice_wine)))
   • 총 시간 복잡도 : O(N × log(max(rice_wine)))
     • N 최대 10,000, max(rice_wine)가 2³¹ 정도이므로, log(2³¹) = 약 31회 정도 반복
     • 약 10,000 × 31 = 310,000번 정도 연산하므로 충분히 시간내에 가능합니다.

알고리즘 선택

막걸리 용량(x ml)을 결정하는 문제에서, “x ml를 줄 수 있느냐”의 여부를 판단하기 때문에 이분 탐색으로 접근해 보겠습니다.

---

📌 코드 설계하기

• 문제의 Input을 받습니다.
• 0으로 나누는 것을 피하고자 left = 1로 초기화합니다.
• right = max(rice_wines)로 초기화합니다.
• 막걸리 용량을 나눌 수 있는 최댓값을 저장하기 위해 ans = 0 으로 초기화합니다.
• 최댓값을 구하기 위해 반복문을 반복합니다. ( left <= right )
  
  • 이분 탐색을 위해 중간값을 구합니다.
    • mid = ( left + right ) // 2 
  • 총 몇 명에게 나눠줄 수 있는지, 각 주전자의 막걸리를 mid ml씩 나눈 횟수를 계산하여 합산합니다.
    • serving_count = sum(wine // mid for wine in rice_wines)K = K - 1
  • serving_count 합계가 K 이상이면 mid 값을 ans로 기록하고, 더 큰 값을 탐색합니다.
    • left = mid + 1
  • serving_count 합계가 K 미만이면, mid 값이 너무 큰 것이므로 범위를 낮춥니다.
    • right = mid - 1
• ans 값을 출력하여 K명에게 나눠줄 수 있는 최대 막걸리 용량을 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

• 1회차 : 시간초과
  • 단순 이분 탐색을 적용하여 각 주전자마다 (wine // mid)를 계산
  • serving_count가 정확히 K가 되는 경우에만 ans를 갱신하거나 종료하는 로직을 사용하여 무한 루프로 시간 초과가 발생했습니다.

---

📌 정답 코드

import sys
input = sys.stdin.readline

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

left = 1
right = max(wines)

ans = 0

while left <= right:
    serving_count = 0

    mid = (left + right) // 2
    serving_count = sum(wine // mid for wine in wines)

    if serving_count >= K:
        ans = mid
        left = mid + 1
    else:
        right = mid - 1

print(ans)