[백준] 1166 선물 - 실버 3

https://www.acmicpc.net/problem/1166

 

 

 

주어진 문제는 다음과 같습니다.

 

아이들에게 선물한 같은 크기의 작은 박스를 N개 가지고 있습니다.

모든 작은 박스는 정육면체이고 크기는 A * A * A 입니다.

 

민식이는 이 작은 박스를 크기가 L * W * H 인 직육면체 박스에 모두 넣으려고 합니다.

모든 작은 박스는 큰 박스 안에 있어야 하고 작은 박스의 변은 큰 박스의 변과 평행해야 합니다.

 

---

 

처음에는 문제가 왜 이분탐색인지 이해하지 못했으나

 

주어진 L, W, H 에 대해 최대공약수를 찾고 이를 이분탐색을 통해 A의 최솟값을 0으로 주고 최대값으로 L, W, H에서 최소 값을 주면 N개의 상자를 모두 넣을 수 있게 됩니다. 

 

즉 더 큰 A가 최대공약수의 조건과 N값을 충족할때 포인터를 옮겨 문제를 해결해야 하는 것입니다.

 

import sys
input = sys.stdin.readline

N, L, W, H = map(int, input().split())
start, end = 0, max(L, W, H)

for _ in range(100):
    medium = (start + end) / 2
    count = (L // medium) * (W // medium) * (H // medium)
    if count >= N:
        start = medium
    else:
        end = medium
print("%.10f" %(end))

 

---

 

[결과]