[백준][python] 1166.선물 - Binary Search

• 백준 1166 선물 Silver III
• python
• 문제링크

1166번: 선물

나의 풀이

주어지는 L, W, H에 대한 최대공약수를 찾는다는 느낌으로 접근하면 된다. 여기에 이분탐색을 곁들인. A의 최소값으로 0을 주고, 최대값으로 L, W, H에서의 최소 값을 준다. N개의 상자를 모두 넣을 수 있어야 하기 때문에 더 큰 A가 최대공약수의 조건과 N값을 충족한다면 포인터를 옮겨줘서 탐색을 계속한다. 

import sys

N, L, W, H = map(int, sys.stdin.readline().split())
S, E = 0, max(L, W, H)

for _ in range(10000):
    M = (S + E) / 2
    count = (L // M) * (W // M) * (H // M)
    if count >= N:
        S = M
    else:
        E = M

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