[Python/파이썬] 백준 1166번 선물

1166번: 선물

 

코드

n, l, w, h = map(int, input().split())

s, e = 0, max(l, w, h)
ans = 0
for _ in range(100):
    mid = (s+e)/2
    boxes = (l//mid)*(w//mid)*(h//mid)
    if boxes < n:
        e = mid
    else:
        ans = mid
        s = mid
print(ans)

 

이분탐색의 시간복잡도는 $O(logN)$으로 0~1,000,000,000 범위를 탐색한다면 반복문을 100번 이내로 도는 것은 명확하다.

여기서 우리가 구하는 박스의 한 변 길이는 소수가 나올 수도 있으므로 mid를 구할 때는 // 연산이 아닌 / 연산을 수행한다. 그리고 boxes값에 따라 s 또는 e의 값을 조정할 때, 정수 범위에서 이분탐색을 하던 것처럼 mid 값에 1을 더하거나 빼지 않고 mid값만 s 또는 e에 넣어준다.

이렇게 구하면 소수점 자리를 가진 수도 이분탐색으로 구할 수 있다.