[백준][1166] 선물

• Problem Link : https://www.acmicpc.net/problem/1166

문제

• L x W x H 인 큰 직유면체 상자에 A x A x A 정육면체 상자를 N개 모두 담으려고 한다.
• N, L, W, H가 주어질 때 A의 최대값을 구하여라

입력

• 첫째 줄에 네 정수 N, L, W, H가 주어진다.

출력

• A의 최댓값을 출력한다.

이 문제를 보고 처음 들었던 생각은 그냥 직육면체의 상자의 가장 작은변을 정육면체의 최대 길이로 삼은 다음에 1씩 낮추면서 N개가 담길 때까지 정육면체 상자를 줄이면 된다고 생각했으나 이 문제의 제일 중요한 점은 A가 정수가 아니라는 것이다.

문제의 출력에서 절대/상대 오차는 $10^{-9}$까지 허용한다는 문장이 괜히 있던 것이 아니었다.

위 방식대로 문제를 풀다가 예제 입력 4에서 A의 최댓값이 52.3 정도 나와야 한다는 것을 보고 이렇게 1씩 줄여서 정육면체의 길이를 찾으면 안된다고 생각하고 방향을 바꿨다.

그렇다고 모든 실수를 $10^{-9}$ 범위까지 다 넣는 것은 불가능했다. 따라서 이분 탐색 방법을 써서 최대한 반씩 줄여나가면서 허용 오차 안까지 최대한 A의 최댓값에 가까워지도록 했다. 이분 탐색의 가장 좋은 점은 시간 복잡도가 O(log N)으로 굉장히 빠르게 탐색이 가능하다는 점이고 이 문제처럼 실수를 찾는 경우에는 반복을 하면 할수록 답에 더 가까워 질 수 있다는 점이다. 따라서 다음과 같이 이분 탐색을 설정했다.

• A가 중간값(mid)일 때 담을 수 있는 정육면체의 수가 n보다 크거나 같을때, 여유공간이 좀 있다는 뜻이므로 A를 더 키워서 최대값에 가까워지도록 한다.
  - 따라서 left = mid로 설정한다.
• A가 중간값(mid)일 때 담을 수 있는 정육면체의 수가 n보다 작을때, A가 너무 커서 정육면체를 모두 담을 수 없다는 뜻이므로 A를 줄여서 n개가 모두 담기도록 한다.

따라서 이분 탐색 방식으로 가되 반복을 약 1000번 정도해서 결과 값을 확인하도록 다음과 같이 코딩했다.

for _ in range(1000):
    mid = (left + right) / 2
    if (l // mid) * (w // mid) * (h // mid) >= n:
        left = mid
    else:
        right = mid

오류 및 해결

원래는 반복문 없이 left와 right의 오차가 $10^{-9}$보다 클 때 반복하도록 했으나 시간 복잡도가 초과되었다.

while abs(left - right) >= 10 ** (-9): #시간 복잡도 초과

그래서 단순 for문으로 1000번 반복했더니 해결되서 반복횟수를 좀 줄여보고자 100번 반복으로 줄였더니 그래도 해결이 되었다.

for _ in range(100): #100번으로도 오차를 충분히 줄일 수 있다.

이 문제를 풀고 단순 100번 반복으로도 오차를 $10^{-9}$보다 작게 값을 찾아내는 이분 탐색의 효율이 얼마나 좋은지 다시금 느끼게 되었다.

코드

import sys

n, l, w, h = map(int, sys.stdin.readline().split())

left = 0
right = max(l, w, h)

for _ in range(100):
    mid = (left + right) / 2
    if (l // mid) * (w // mid) * (h // mid) >= n:
        left = mid
    else:
        right = mid


print("%.10f" % (right))