과자 나눠주기 [백준]

🧠 TIL - 이진탐색 과자 나눠주기

오늘은 다시 한 번 이진탐색 개념을 정리했다.
직접 구현할 땐 while문 범위나 mid 조정에서 종종 헷갈려서, 이번에 완전히 패턴을 잡아놔야겠다고 생각했다.

📌 개념

이진 탐색은 정렬된 탐색 범위 내에서 특정 조건을 만족하는 값을 찾는 방식이다. 중간값(mid)을 기준으로 탐색 범위를 반씩 줄여가며, 조건을 만족하는지 확인하고 범위를 조정한다.

🧩 기본 구조

start = 최소값
end = 최대값
answer = 0

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

    if 조건 만족:
        answer = mid
        start = mid + 1  # 더 크게 도전
    else:
        end = mid - 1    # 줄여야 함

❓ 왜 이렇게 하는가

• start <= end: 탐색이 끝나기 전까지
• 조건을 만족: 일단 저장하고 더 큰 쪽 탐색
• 조건 불만족: 무조건 줄여야 하니까 end 감소

🧪 예제: 막대과자 나누기

조카한테 막대과자를 나눠줄 때, 길이가 동일해야 하고 합칠 수는 없고 자를 수만 있다. 조카 1명에게 줄 수 있는 막대과자의 최대 길이를 구하는 문제.

def can_distribute(cookies, length, m):
    cnt = 0
    for c in cookies:
        cnt += c // length
    return cnt >= m

def solve(m, cookies):
    start, end = 1, max(cookies)
    answer = 0

    while start <= end:
        mid = (start + end) // 2
        if can_distribute(cookies, mid, m):
            answer = mid
            start = mid + 1
        else:
            end = mid - 1

    return answer

🧠 정리

• 조건을 만족하면 answer에 저장하고 더 크게 도전
• 조건을 만족 못하면 더 작게 줄이기
• 정답 후보는 answer에 따로 저장 (중간값이 정답 아닐 수 있음)
• 문제에 따라 최소 만족값 or 최대 만족값을 찾는 방식으로 적용

📝 기억해둘 것

• 이진 탐색은 단순 값 찾기 외에 최적의 값 찾기용 파라메트릭 서치로 자주 사용됨
• mid 기준 탐색 → 가능? → 범위 조정 흐름 익숙해질 것
• 문제마다 탐색 조건이 다르니, 가능 조건만 함수로 분리해두면 좋음