사용 개념: 매개변수 탐색.
이 방법을 떠올리는 신호는 “가장 작은/큰 ~을 구하라”인데 답의 범위가 너무 넓어 하나씩 해 볼 수 없는 문제다. 늘 같은 네 하위목표로 푼다.
- 판정 질문 만들기: 답을 x로 정해 두고 “x면 되나?”를 예·아니오로 묻는다.
- 방향 정하기: x가 커질 때 대답이 어느 쪽으로 한 번만 바뀌는지 보고, 최소형(아니오…예)인지 최대형(예…아니오)인지 정한다.
- 범위 정하기: 답이 반드시 들어 있는 [lo, hi]를 잡는다. 최소형이면 hi가, 최대형이면 lo가 “확실히 되는 값”이어야 한다.
- 판정 함수 짜고 틀에 넣기: “x면 되나?”를 빠르게 계산하는 함수를 짜고, 방향에 맞는 틀에 넣는다.
문제 1 · 완전한 풀이
쪽수가 [10, 20, 30, 40]인 책 네 권을 이 순서대로 2명에게 나눠 준다. 한 사람은 연달아 놓인 책만 받는다. 가장 많이 받는 사람의 쪽수를 가장 작게 하면 몇 쪽인가?
- 판정 질문 만들기: “한 사람이 많아야 x쪽까지 받으면 2명 이하로 나눌 수 있나?”
- 방향 정하기: x가 크면 한 사람이 더 많이 받을 수 있어 더 쉽다. 대답은 아니오…아니오 예…예다. 최소형이다.
- 범위 정하기: lo = 40(가장 두꺼운 책). 이보다 작으면 그 책을 받을 사람이 없다. hi = 100(전체 합). 한 사람이 다 받으면 반드시 된다.
- 판정 함수 짜고 틀에 넣기: 앞에서부터 한 사람에게 담다가 x를 넘기면 다음 사람으로 넘어간다. 앞사람에게 되도록 많이 주는 것은 손해가 아니다. 필요한 사람 수가 2 이하인지 본다.
def people_needed(books, cap):
cnt, cur = 1, 0
for b in books:
if cur + b > cap: # 이 책을 넣으면 넘친다 → 다음 사람
cnt, cur = cnt + 1, 0
cur += b
return cnt
lo, hi = max(books), sum(books)
while lo < hi: # 최소형 틀
mid = (lo + hi) // 2
if people_needed(books, mid) <= 2: hi = mid
else: lo = mid + 1
# lo == 60
물어보는 x는 70(예), 55(아니오), 63(예), 59(아니오), 61(예), 60(예) 순서다. 답은 60쪽이다. [10, 20, 30]과 [40]으로 나눈다.
문제 2 · 마지막 하위목표를 채운다
좌표 [1, 2, 8, 4, 9]에 집이 있다. 공유기 3개를 서로 다른 집에 놓는다. 가장 가까운 두 공유기 사이의 거리를 가장 크게 하면 얼마인가?
- 판정 질문 만들기: “모든 공유기 사이를 x 이상 떨어뜨려 3개를 놓을 수 있나?”
- 방향 정하기: x가 작을수록 쉽다. 대답은 예…예 아니오…아니오다. 최대형이다.
- 범위 정하기: 집을 정렬하면 [1, 2, 4, 8, 9]다. lo = 1(집이 모두 다르니 1은 늘 된다), hi = 9 − 1 = 8.
- 판정 함수 짜고 틀에 넣기: __
답
첫 집에 하나 놓고, 앞으로 가며 직전 공유기에서 x 이상 떨어진 첫 집마다 놓는다. 놓은 개수가 3 이상이면 된다. 최대형이니 mid를 올림 (lo + hi + 1) // 2로 잡고, 되면 lo = mid, 안 되면 hi = mid - 1이다.
답은 3이다. x = 3이면 1, 4, 8에 놓인다. x = 4면 1, 8 두 곳뿐이라 안 된다.
문제 3 · 하위목표 절반을 채운다
바나나 더미가 [3, 6, 7, 11]개 있다. 한 시간에 한 더미만 골라 x개까지 먹는다. 더미에 x개보다 적게 남았으면 그 시간에는 그것만 먹는다. 8시간 안에 모두 먹는 가장 작은 x는?
- 판정 질문 만들기: “한 시간에 x개씩 먹으면 8시간 안에 다 먹나?”
- 방향 정하기: __
- 범위 정하기: lo = 1, hi = 11(가장 큰 더미). x = 11이면 더미마다 한 시간이라 4시간이면 된다.
- 판정 함수 짜고 틀에 넣기: __
답
-
x가 크면 더 빨리 먹으니 더 쉽다. 아니오…예의 최소형이다.
-
더미 p개를 먹는 데 ⌈p / x⌉시간이 든다. 파이썬으로는
(p + x - 1) // x다. 합이 8 이하인지 본다. 최소형 틀에 넣는다.
답은 4다. x = 4면 1 + 2 + 2 + 3 = 8시간, x = 3이면 1 + 2 + 3 + 4 = 10시간이다.
문제 4 · 혼자 풀기
기계 세 대가 물건 하나를 각각 2초, 3초, 7초에 만든다. 세 대가 동시에 돌 때 물건 8개를 만드는 가장 짧은 시간은?
답
판정 질문은 “T초 안에 8개 이상 만드나?”다. T가 크면 더 많이 만드니 최소형이다. 범위는 lo = 1, hi = 16(2초 기계 혼자 8개를 만드는 시간)이다.
def made(times, T):
return sum(T // t for t in times)
lo, hi = 1, 16
while lo < hi:
mid = (lo + hi) // 2
if made([2, 3, 7], mid) >= 8: hi = mid
else: lo = mid + 1
# lo == 9
T = 8이면 4 + 2 + 1 = 7개, T = 9이면 4 + 3 + 1 = 8개라 답은 9초다.