[백준] 1166 - 선물

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

 

이분탐색 심화 개념을 사용해야 하는 문제.. (나도 알고 싶지 않았다)

문제 자체는 간단하다.

어떤 정육면체 N개를 W*H*L 직육면체 안에 넣고자 할 때, 이 정육면체의 한변의 길이를 최대한 늘리는 것이 문제 풀이이다.

단순히 직육면체와 같은 부피를 갖는 N개 정육면체에 대한 한변 길이 구하기로는 풀 수 없다. 극단적으로 얇은데 큰 직육면체를 생각하면 된다. (1 x 10억 x 10억)

 

내가 맨 처음 생각한 풀이는 (알고보니 정해였지만) 이분탐색이다.

주어진 직육면체의 세 변 중 가장 짧은 변의 길이를 반씩 나누면서 그 변의 길이를 정육면체의 변의 길이로 할 때 N개 이상의 상자를 담을 수 있는지 계산하는 것이다.

 

s = 0, e = min(W, H, L) 로 두고, 담을 수 있으면 s = mid 담을 수 없으면 e = mid 로 처리한다.

 

나는 이 풀이로 풀 수 없다고 생각해서 다른 풀이를 고안했다.

왜냐하면 이 풀이는 '언제 이분탐색을 멈출 지' 종료 조건을 알 수 없기 때문이다.

하지만 정답은 이 풀이가 맞았다.

어차피 10^-9 오차 범위 안으로 들어오기만 하면 되므로, 그 오차범위 안에 들어올 때까지 이분탐색을 돌리는 것이다.

(즉, e - s < 10^-9 이면 된다.)

 

그런데 이 조건을 걸어도 (e-s) 가 항상 10^-9보다 커서 반복이 안끝나는 경우가 있기도 하다보니, 보통은 정해진 횟수(200번이면 충분하다고..)를 걸고 돌린다고 한다.

이 문제의 정해도 정해진 횟수만큼 반복을 돌면서 이분탐색을 돌리는 것 이었다. (이런 식으로 풀기도 한다니..)

자세한 내용은 https://witch.work/posts/binary-search-next-step 이 글을 참고해보자.

(알아도 좋고 몰라도 좋은 이야기 - 실수 이분탐색 팁)

 

N, L, W, H = map(int, input().split())
s, e = 0, min(L, W, H)
for _ in range(100000):
    mid = (s + e) / 2
    if ((L // mid) * (W // mid) * (H // mid)) >= N:
        s = mid
    else:
        e = mid

print(s)

 

(위 코드는 그냥 10만번 반복을 돌렸는데, 위에 적은대로 200번만 돌려도 통과한다.)

 

 

내가 이분탐색 풀이는 답을 구할 수 없다고 생각해서 떠올린 다른 풀이는 이 문제의 예제 입력 4번의 정답을 봤을 때 이 문제의 정답이 되는 A의 길이는 L, H, W 셋 중 적어도 하나를 나누어 떨어지게 하는 값이라는 점에서 착안하고 풀이를 떠올렸다.

만약 셋 중 적어도 하나를 나누어떨어지게 하지 않는다면 A를 늘리는 것이 최적이기 때문이다.

 

L, H, W 를 1, 2, 3, ... 으로 1씩 증가시키는 값으로 매번 나누어 A의 후보를 구하고, 그 모든 경우의 수 중 min(L, H, W) 이하인 값들에 대해 큰 값부터 하나씩 시도하면서 N 이상의 상자를 담는 순간에 멈추는 것이 나의 풀이였다.

 

def calculate(A):
    return (L // A) * (W // A) * (H // A)

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

L_count, W_count, H_count = 1, 1, 1
answer = min(L, W, H)
while True:
    result = calculate(answer)
    if result >= N:
        print(answer)
        exit(0)

    now_L = L / L_count
    while now_L >= answer:
        L_count += 1
        now_L = L / L_count

    now_W = W / W_count
    while now_W >= answer:
        W_count += 1
        now_W = W / W_count

    now_H = H / H_count
    while now_H >= answer:
        H_count += 1
        now_H = H / H_count

    answer = max(now_L, now_W, now_H)

 

이 풀이는 예제 입력 4개를 모두 올바르게 구하지만 6% 에서 틀렸다.

혹시 실수 오차 때문인가 싶어서 Decimal 을 떡칠하여 제출했으나 14% 에서 틀렸다.

나눗셈을 하도 반복하다보니 Decimal 을 써도 결국 오차를 피해갈 수는 없는 건가 싶다..

 

개인적으로 이런 문제는 PS를 즐기고 싶을 때 이렇게도 풀 수 있구나 하는 아이디어를 얻어갈 때 좋은 것 같다.

(너무 마이너한 주제라고 생각한다)