[BOJ][Python]1166 풀이

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

1166번: 선물

n, l, w, h = map(int, input().split())
top, bot = min(l, w, h), 0
for _ in range(100):
    mid = (top + bot)/2
    if (l//mid)*(w//mid)*(h//mid) >= n:
        bot = mid
    else:
        top = mid
print(f'{top:.10f}')

개인적으로 마음에 들지 않는 문제입니다. 사실 해당 문제는 이론적으로 이분 탐색이 아닌 방정식으로도 풀려야 하는 문제입니다. 두께가 주어지지 않은 직육면체 박스의 안에 N개의 최대 크기의 정육면체를 채워넣는다는 것은 직육면체와 동일한 부피를 갖는 N개의 정육면체를 만든다는 것과 같은 말이 됩니다. 그렇기 때문에 수식을 세워보면 (L * W * H / n)^(1/3)의 길이를 갖는 정육면체가 나와야 하는 것을 알 수 있죠. 하지만 아무래도 이분 탐색에서 몫연산 때문에 생기는 오차로 인해 해당 식으로 구하는 값보다 훨씬 작은 값이 나오는 것을 알 수 있습니다. 애초에 이분탐색이 아닌 풀이로는 정답을 낼 수 없는 구조의 문제를 만들어 놨네요.

 

이분탐색으로 푸는 것도 좀 애매한게 1e-9까지의 오차를 감안하기 때문에 평소처럼 while 반복문으로 탈출을 시키려면 주어진 입력이 큰 경우 너무 많은 연산량 때문에 시간초과가 나서 for 반복문으로 횟수를 지정해서 돌려야합니다(40번 까지는 잘 돌아갑니다). 물론 항상 1을 더하거나 빼서 범위를 축소시키는게 합리적이라고 생각하지는 않았지만 과하게 오차를 많이 준 것이라는 생각이 드네요. 어차피 if문에서 mid를 세번이나 몫연산을 시키면서 오차가 터무니 없이 커지기 때문에 문제로서도 가치가 적다고 생각합니다(마치 문제를 만드는 사람이 큰 박스 안에 작은 박스를 채워넣을 때 당연히 빈 공간이 생기는 걸 고려해야지? 라는 생각에 사로잡혀서 만든 것 같다는 느낌이 든다고나 할까요). 정말 오로지 이분탐색 연습을 시키기 위해 만든 문제같다는 생각이 드네요. 상당히 아쉽습니다.