백준 1166 선물 / python

문제 : 1166

풀이 point

L, W, H 크기의 직육면체에 A, A, A 크기의 정육면체를 넣기 위해서는 가로 세로 높이를 따로 따로 생각해보면 된다. 가로 W에 A를 넣고, 세로 L에 A를 넣고, 높이 H에 A를 넣는다면
L/A, W/A, H/A 만큼의 크기를 차지한다. 즉, (L/A) (W/A) (H/A) >= N인지 확인하며 최대값을 찾아나가면 된다.

다만, 문제를 보면 N범위가 굉장히 크다는 것을 알수 있다.

1 ≤ N ≤ 1,000,000,000

즉 선형 탐색으로는 시간 내에 불가능하고 이분 탐색을 활용하여 찾아낼 수 있다. 그리고 문제에서 정수가 아닌 실수까지 포함이 되고 있기 때문에 다음과 같이 실수 이분 탐색을 진행해야한다.

풀이 코드

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

st = 0; end = max(max(L, W), H)

for i in range(10000):
  mid = (st+end)/2

  if (L//mid) * (W//mid) * (H//mid) >= N:
    st = mid
  else:
    end = mid
  
print("%.10f" %st)