[백준/파이썬][Gold V] 종이 접기 - 12979

[Gold V] 종이 접기 - 12979

문제 링크

성능 요약

메모리: 109544 KB, 시간: 92 ms

분류

브루트포스 알고리즘, 수학

제출 일자

2025년 2월 4일 21:50:50

문제 설명

W×H 크기의 종이가 있다. 지금 현정이가 필요한 종이의 크기는 넓이가 A인 종이이다. 따라서, 종이를 접어서 넓이가 A인 종이를 만들려고 한다.

종이는 직선을 기준으로 접어야하며, 다음과 같은 두 가지 조건을 지켜야 한다.

• 종이를 접는 기준선은 직사각형의 한 변과 평행해야 한다.
• 종이를 접은 후에도 W와 H는 정수가 되어야 한다.

예를 들어, 5×3 크기의 종이가 있는 경우에, 너비를 기준으로 4가 되는 선으로 종이를 접으면 4×3 크기의 종이를 접게 된다. 이제, 높이를 기준으로 1이 되는 선을 기준으로 종이를 접어서 5×2 크기의 직사각형을 만들 수 있다.

W, H, A가 주어졌을 때, 넓이가 A가 되게 접을 수 있는지 없는지 구하고, 접을 수 있는 경우에는 접어야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 W, H, A가 주어진다. (1 ≤ W, H ≤ 1,000,000,000, 1 ≤ A ≤ 100,000)

출력

W×H 크기의 종이를 접어서 넓이가 A가 되게 만들 수 있으면 접는 횟수의 최솟값을, 만들 수 없으면 -1을 출력한다.

풀이

def min_folds_needed(L, target):
    """
    L에서 target까지 줄이기 위해 필요한 최소 접기 횟수를 구한다.
    한 번 접으면 최대로 많이 줄일 수 있는 값은 ceil(L/2)이다.
    target이 L보다 클 수는 없으므로, 만약 target > L이면 매우 큰 값을 반환한다.
    """
    if target > L:
        return float('inf')
    folds = 0
    current = L
    # current가 target보다 작거나 같아질 때까지 최적으로 접었을 때의 값으로 갱신한다.
    while current > target:
        current = (current + 1) // 2  # ceil(current/2)
        folds += 1
    return folds

def solve():
    W, H, A = map(int, input().split())

    # 만약 A가 원래 종이의 넓이보다 크면 접어서 A를 만들 수 없다.
    if A > W * H:
        print(-1)
        return

    # 원래 종이의 넓이가 이미 A라면 접을 필요가 없다.
    if A == W * H:
        print(0)
        return

    best = float('inf')
    found = False
    # A의 약수 쌍 (w, h)를 모두 찾는다.
    for d in range(1, int(A ** (1/2)) + 1):
        if A % d != 0:
            continue
        e = A // d
        # 후보 1: 최종 크기가 (d, e)가 되어야 하는 경우.
        if d <= W and e <= H:
            folds_w = min_folds_needed(W, d)
            folds_h = min_folds_needed(H, e)
            candidate = folds_w + folds_h
            if candidate < best:
                best = candidate
                found = True
        # 후보 2: (e, d)인 경우 (d와 e가 다르면 회전한 경우)
        if d != e:
            if e <= W and d <= H:
                folds_w = min_folds_needed(W, e)
                folds_h = min_folds_needed(H, d)
                candidate = folds_w + folds_h
                if candidate < best:
                    best = candidate
                    found = True

    if found:
        print(best)
    else:
        print(-1)


if __name__ == '__main__':
    solve()

문제를 풀기 위해서는 "접기"라는 연산이 한 변의 길이를 어떻게 줄일 수 있는지를 먼저 이해해야 합니다.

예를 들어, 한 변의 길이가 $L$ 인 직사각형에서, 종이를 한 번 접을 때는 직선 (접는 기준선)을 $L$의 어느 정수 위치 $x$ (단, $1\leq x\leq L - 1$) 에 놓고 접게 됩니다. 이때 접은 후의 "폭"은 두 부분 중 큰 쪽의 길이가 됩니다. 즉

$$ L \to L' = max(x, L - x) $$

인데, 이때 $x$ 를 어떻게 선택하느냐에 따라 $L'$ 는

$$ [L/2] \leq L' \leq L-1 $$

의 임의의 정수값을 만들 수 있음을 알 수 있습니다.

즉, 한 변에 대해 "접기" 연산은 $L$을 임의의 정수 $t$로 줄이는 것이 가능하며, 단 조건은 $ t \geq [L/2] $ 를 만족해야 합니다. 여러 번 접으면 최대로 많이 줄일 수 있는 값은 "최적으로 많이 줄였을 때" $L$이 $[L/2]$가 되고, 다시 접으면 $[[L/2]/2] ... $ 이런 식입니다.

따라서, 한 변 $L$에서 목표값 $t (t \leq L) $ 를 만들기 위해 필요한 "최소 접기 횟수"는, $k$번 접었을 때 "최소로 만들 수 있는 값"

$$ f(L, k) = [[ \underbrace{ \cdots }_{k \text{번}} [L/2] \cdots /2] $$

가 $t$ 이하가 되는 최소 $k$ 와 같습니다. (접은 후에는 그 변에 대해서 $f(L, k) 이상 $L$ 사이의 모든 정수가 만들 수 있으므로,) 실제로 우리는 

• 만약 $t = L$ 이면 접지 않아도 되므로 0회.
• $t < L$ 인 경우, $L$에서 "최적으로 많이 줄였을 때" $f(L,k)$ 가 $t$ 이하가 되는 최소 $k$가 바로 필요한 최소 접기 횟수입니다.

종이 전체는 $W \times H$ 크기에서 시작하며, 우리의 목표는 넓이가 $A$인 종이를 만드는 것입니다. 최종 직사각형의 두 변은 $w$ 와 $h$ (양의 정수)여야 하고 $w \times h = A$ 여아 합니다. 또한, 종이를 접는 연산은 두 변에 대해 독립적으로 적용할 수 있으므로, $W$ 에서 $w$를, $H$ 에서 $h$ 를 만드는 데 필요한 접기 횟수를 각각 구한 후 합하면 됩니다.

다만 최종 $w, h$가 원래 종이의 방향에 맞게 들어가야 하므로

• $w \leq W$ 이고 $h \leq H$
• 또는 (종이 회전이 가능하다고 볼 수 있으므로) $w \leq H$ 이고 $h \leq W$ 인 경우만 고려하면 됩니다.

$A$의 최댓값이 ${10}^{5}$이므로 $A$의 약수(즉, 가능한 $w, h$ 후보)는 충분히 작게 반복할 수 있습니다.