이분 탐색 - 과자 나눠주기/공유기 설치/용돈 관리/두 용액

전형적인 이분탐색 유형

16401 과자 나눠주기

m, n = map(int, input().split())  # 조카의 수, 과자의 수
snacks = list(map(int, input().split()))

start = 1
end = max(snacks)

result = 0
while (start <= end):
    mid = (start + end) // 2   # 조카들에게 나눠줄 과자 길이
    total = 0  # mid 길이로 나눠줄 수 있는 조카 수
    
    total = sum(snack // mid for snack in snacks)
    if total < m:
        end = mid - 1
    else:
        start = mid + 1
        result = mid

print(result)
    

📌 배운점

sum이 내장함수라서 c로 구현되어 있기 때문에 sum이 빠르다

cnt = sum(snack//mid for snack in snacks)

시간초과 나는 코드

    for snack in snacks:
      cnt += snack//mid

2110 공유기 설치

import sys

input = sys.stdin.readline
n, c = map(int, input().split())
home = []
for _ in range(n):
    home.append(int(input()))
home.sort()

start = 1   # 최소 거리
end = home[-1] - home[0] # 최대 거리

while start <= end:
    mid = (start + end) // 2
    current = home[0]
    cnt = 1
    
    for i in range(1, len(home)): # 예제1 기준 1 ~ 4, len(home)인 5는 포함x
        if home[i] >= current + mid: # 설치 가능
            cnt += 1
            current = home[i]
    if cnt >= c:            # c개보다 더 많이 설치되어 최소 거리를 늘린다
        start = mid + 1
    else:                   # c개보다 적게 설치되어 최대 거리를 줄인다
        end = mid - 1
print(end)

---

6236 용돈 관리

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
budgets = [int(input()) for _ in range(n)]
start = min(budgets)
end = sum(budgets)

while start <= end:
    mid = (start + end) // 2  # 인출할 금액
    now = mid  # 현재 가진 돈
    draw = 1   # 인출 횟수
    
    for budget in budgets:
        if now < budget:  # 가진 돈이 부족하면 돈 인출
            draw += 1
            now = mid
        now -= budget
    if draw > m or mid < max(budgets):  # 인출 횟수가 m번 보다 많거나 인출 금액이 적음
        start = mid + 1
    else:    # 인출 횟수가 m번보다 적거나 같음
        end = mid - 1
        k = mid
print(k)

문제 풀이가 생각이 안나서 이블로그를 참고했다.

---

2470 두 용액

n = int(input())
waters = list(map(int, input().split()))
waters.sort()

start = 0
end = len(waters)-1

# print(waters)
cur = waters[start] + waters[end]
ans1 = start
ans2 = end

while start < end:
    mix = waters[start] + waters[end]
    if abs(mix) < abs(cur):
        ans1 = start
        ans2 = end
        cur = mix
    
    if mix < 0:
        start += 1
    else:
        end -= 1
print(waters[ans1], waters[ans2])

초기화가 중요했던 문제