백준 27743번: 어려운 하노이 탑

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

27743번: 어려운 하노이 탑

---

$N=4$, $M=3$ 정도인 상황을 시뮬레이션 돌려보면 감을 잡을 수 있습니다.

 

우선, 각 기둥을 왼쪽에서부터 peg 1, 2, 3 이라고 하겠습니다.

 

그리고 크기 $N$의 원판이 번호 $1$부터 $M$에 대해 내림차순으로 쌓인 상황을 $N \downarrow$로 표현하겠습니다.

 

다시 말해 문제에서 주어진 초기 상황이 다음과 같이 표현된다는 뜻입니다.

$$ \begin{matrix} 1 \downarrow \\ 2 \downarrow \\ \vdots \\ N \downarrow \\ peg1 & peg2 & peg 3 \end{matrix} $$

---

$N=4, \;\; M > 1$ 일 때 원판을 최소한으로 움직이는 상황을 요약하면 다음의 흐름입니다.

$$ \begin{pmatrix} 1 \downarrow \\ 2 \downarrow \\ 3 \downarrow \\ 4 \downarrow \\ peg1 & peg2 & peg 3 \end{pmatrix} \rightarrow \begin{pmatrix} & & 1 \downarrow \\ & & 2 \downarrow \\ 4 \downarrow & & 3 \uparrow \\ peg1 & peg2 & peg 3 \end{pmatrix} \rightarrow \begin{pmatrix} & & 1 \downarrow \\ & & 2 \downarrow \\ &4 \uparrow & 3 \uparrow \\ peg1 & peg2 & peg 3 \end{pmatrix} $$

$$ \rightarrow \begin{pmatrix} 1 \downarrow \\ 2 \downarrow \\ 3 \downarrow & 4 \uparrow & \\ peg1 & peg2 & peg 3 \end{pmatrix} \rightarrow \begin{pmatrix} 1 \downarrow \\ 2 \downarrow \\ 3 \downarrow & & 4 \downarrow \\ peg1 & peg2 & peg 3 \end{pmatrix} \rightarrow \begin{pmatrix} & & 1 \downarrow \\ & & 2 \downarrow \\ & & 3 \downarrow \\ & & 4 \downarrow \\ peg1 & peg2 & peg 3 \end{pmatrix} $$

바로 마지막 부분만 살펴보면 DP를 쓸 수 있을 것처럼 보이는데, 일반적인 하노이 탑 문제를 풀 때처럼 접근하면 될까요?

 

이 부분을 살펴보겠습니다.

$$ \begin{pmatrix} 1 \downarrow \\ 2 \downarrow \\ 3 \downarrow \\ 4 \downarrow \\ peg1 & peg2 & peg 3 \end{pmatrix} \rightarrow \begin{pmatrix} & & 1 \downarrow \\ & & 2 \downarrow \\ 4 \downarrow & & 3 \uparrow \\ peg1 & peg2 & peg 3 \end{pmatrix} $$

무슨 과정을 거쳐서 이렇게 된 걸까요?

 

우선 화살표의 방향을 봤을 때, 크기 $3$의 원판은 1번씩만 움직였고, 크기 $2$, $1$의 원판들은 짝수번 움직였다고 짐작할 수 있습니다.

 

실제로 이동과정이 다음과 같습니다.

$$ \begin{pmatrix} 1 \downarrow \\ 2 \downarrow \\ 3 \downarrow \\ 4 \downarrow \\ peg1 & peg2 & peg 3 \end{pmatrix} \rightarrow \begin{pmatrix} 2 \downarrow & & \\ 3 \downarrow & & \\ 4 \downarrow & & 1 \uparrow \\ peg1 & peg2 & peg 3 \end{pmatrix} \rightarrow \begin{pmatrix} 3 \downarrow & & \\ 4 \downarrow & 2 \uparrow & 1 \uparrow \\ peg1 & peg2 & peg 3 \end{pmatrix} $$

$$ \rightarrow \begin{pmatrix} 3 \downarrow & 1 \downarrow & \\ 4 \downarrow & 2 \uparrow & \\ peg1 & peg2 & peg 3 \end{pmatrix} \rightarrow \begin{pmatrix} & 1 \downarrow & \\ 4 \downarrow & 2 \uparrow & 3 \uparrow \\ peg1 & peg2 & peg 3 \end{pmatrix} \rightarrow \begin{pmatrix} 1 \uparrow & & \\ 4 \downarrow & 2 \uparrow & 3 \uparrow \\ peg1 & peg2 & peg 3 \end{pmatrix} $$

$$ \rightarrow \begin{pmatrix} 1 \uparrow & & 2 \downarrow \\ 4 \downarrow & & 3 \uparrow \\ peg1 & peg2 & peg 3 \end{pmatrix} \rightarrow \begin{pmatrix} & & 1 \downarrow \\ & & 2 \downarrow \\ 4 \downarrow & & 3 \uparrow \\ peg1 & peg2 & peg 3 \end{pmatrix} $$

이때 특히, 크기 $2$인 원반이 2번, 크기 $1$인 원반이 4번 움직인다는 걸 관찰할 수 있습니다.

 

이를 $N$ 과 $M$ 에 대해 일반화하면,

 

크기 $N-1$ 인 원반이 1번, 크기 $N-2$ 인 원반이 2번, $\cdots$, 크기 $1$ 인 원반이 $2^{N-2}$번 움직입니다.

 

크기 별로 원반은 $M$ 개 있으므로, 이 과정에서 이동횟수는 $M \times \left ( 2^{N-1} - 1 \right )$ 입니다.

 

이상의 과정을 $B$ 과정이라고 하면, $B$ 과정은 2회 반복됩니다. 그리고 $B$ 과정의 이동횟수는 $B_{N,M}=M \times \left ( 2^{N-1} - 1 \right )$ 라고 하겠습니다.

---

전체 최소 이동횟수를 $A_{N,M}$라고 하면 $M > 1$ 일 때,

$$ A_{N,M} = B_{N,M} + M + B_{N,M} + M + A_{N-1,M} $$

라는 식이 성립합니다.

 

초기항이

$$ A_{1,M} = 2M - 1 $$

임을 이용하여 점화식을 풀면

$$ A_{N,M} = 2M \times \left ( 2^{N} - 1 \right ) - 1 $$

이 나옵니다.

---

한편, 언뜻 생각하면 위 식에 $M=1$을 대입하여도 올바른 식이 나와야 할 것 같지만, $M=1$의 경우 오름차순과 내림차순이 올바르게 적용되기 힘듭니다.

 

그 말은 $B$ 과정이 최소 이동횟수에 포함되지 않는다는 뜻이며,

 

따라서 $M > 1$일 때의 점화식이 성립하지 않고,

$$ A_{N,1} = 2^{N} - 1 $$

이 됩니다.

---

요약하면, 다음을 구현하면 되겠습니다.

$$\begin{equation} A_{N,M} = \begin{cases} 2^{N} - 1, & \textrm{if } M = 1\\ 2M \left ( 2^{N} - 1 \right ) - 1, & \textrm{otherwise} \end{cases} \end{equation}$$

다음은 제 코드입니다.

#include <stdio.h>
#define mod 1000000007ull
typedef unsigned long long ull;

ull power_modular (ull X, ull Y);

int main() {
    
    long long N, M;
    scanf("%lld %lld", &N, &M);
    
    ull answer;
    if (M == 1) {
        answer = power_modular(2, N) + mod - 1;
    }
    else {
        answer = M * (power_modular(2, N + 1) + mod - 2) + mod - 1;
    }
    printf("%llu", answer % mod);
    
    return 0;
}

ull power_modular (ull X, ull Y) {
    ull result = 1;
    while (Y) {
        if (Y % 2) {
            result = result * X % mod;
        }
        X = X * X % mod;
        Y /= 2;
    }
    return result;
}

(C11, 0ms, 1116KB, 제출번호 67336747)

---