[백준] 1166 선물

문제

• AxAxA 크기의 N개 박스들을 LxWxH 직육면체 박스에 모두 넣으려고 할 때, A의 최댓값은?
  • 1 <= N, L, W, H <= 1,000,000,000
• 작은 박스의 변은 큰 박스의 변과 평행해야 한다.

 

풀이

• 이진 탐색
• 넣을 수 있는 선물 박스의 개수는 $ (L \div A) \times (W \div A) \times (H \div A) $ 이다.
• 따라서 A의 값을 이진탐색으로 범위를 좁혀 찾아나가기
• 문제는 소숫점까지 계산해야한다는 것이라, 범위 조정을 m+1 이 아니라 m 으로 뒀다.
• 그리고 최대 숫자가 1,000,000,000 이므로 100번만 반복해도 충분히 알아낼 수 있다.

 

N, L, W, H = map(int, input().split())

s, e = 0, 1_000_000_000
answer = 0
for i in range(100):
    m = (s+e) / 2

    if (L//m)*(W//m)*(H//m) >= N:
        answer = m
        s = m
    else:
        e = m

print(answer)

 

References

• 백준 1166번
• 2023.04.30 오늘의 문제