[Python, C/C++] 백준 #1914 하노이 탑(재귀 함수)

재귀 함수를 배울 때, 가장 자주 사용하는 예제가 하노이 탑입니다.

 

Hanoi Tower

하노이 탑의 이동 횟수는 다음의 점화식을 통해서 간단하게 구할 수 있습니다.

 

\[ T(1) = 1 \]

\[ T(N) = 2T(N-1) + 1 \]

 

위의 정화식을 풀면 \( T(N) = 2^N - 1 \) 이라는 것을 금방 풀 수 있습니다.

 

프로그램을 파이썬을 이용해서 작성해 보았습니다.  소스는 참고용으로 봐주세요.

"""
//    baekjoon #1914
//        - by Aubrey Choi
//        - created at 2019-07-23
"""
def hanoi(n, a, b, c):
    if n == 0: return
    hanoi(n-1, a, c, b)
    print '%d %d'%(a,b)
    hanoi(n-1, c, b, a)

a = raw_input().split()
n = int(a[0])
print 2**n - 1
if n <= 20:
    hanoi(n, 1, 3, 2)

 

C/C++ 버전은 아래와 같습니다.  C/C++ 버전의 경우에는 문제가 큰 수를 처리하기가 힘듭니다.  64비트 자료형을 사용하고 싶어도 안 되고, 128비트 자료형을 사용해야 합니다.  그래서 조금은 복잡하게 출력을 했습니다.

//----------------------------------------------------------
//    baekjoon #1914 - Honoi Tower
//        - by Aubrey Choi
//        - created at 2020-01-13
//----------------------------------------------------------
#include <stdio.h>

void print(int n)
{
    int v[13],s,i,t,c,rn; char r[40];
    for(s=0,t=n,rn=0;t>0;s++,t-=8) if(t>=8) v[s]=255; else v[s]=(1<<t)-1;
    while(s)
    {
        for(i=s-1,c=0;i>=0;i--) v[i]+=c<<8,c=v[i]%10,v[i]/=10;
        while(s>0&&!v[s-1]) s--;
        r[rn++]=c+'0';
    }
    while(--rn>=0) putchar(r[rn]); putchar('\n');
}
void hanoi(int n, int a, int b, int c)
{
    if(n==1) {printf("%d %d\n", a, b); return;}
    hanoi(n-1, a, c, b);
    hanoi(1, a, b, c);
    hanoi(n-1, c, b, a);
}
int main()
{
    int n;
    scanf("%d",&n);
    print(n);
    if(n<=20) hanoi(n, 1, 3, 2);
}