1914 하노이 탑

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

하노이 탑은 세 개의 기둥으로 이루어진 퍼즐이다. 첫번째 기둥에 N개의 원판들의 쌓여 있고 두 가지 규칙을 지키면서 세번째 기둥으로 옮겨야 한다. 작은 원판은 항상 큰 원판 위에 있어야 하고 한번에 하나씩만 옮길 수 있다. 이를 재귀 호출로 구현할 수 있다. go(n,x,y)를 n개의 원판을 x 기둥에서 y 기둥으로 옮기는 함수로 정의한다. 그러면 먼저 제일 아래 원판을 제외한 n-1개의 원판을 x와 y가 아닌 기둥으로 옮기고 나서 제일 아래 원판을 y로 옮긴다. 마지막으로 임시로 옮겨놓았던 n-1개의 원판을 y위에 쌓는다. 적절히 재귀 함수를 설계하면 모든 과정이 저절로 이루어짐을 알 수 있다.

이 때 점화식을 유도할 수 있다. n-1개의 원판을 두번 옮기고 마지막에 원판 하나를 옮기므로

이 문제에서는 최대 N=100 이므로 일반적인 자료형으로는 구할 수 없다. string으로 큰 수 연산을 구현하였다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
void go(int n,int x,int y)
{
    if(n==0) return;
    go(n-1,x,6-x-y);
    cout<<x<<' '<<y<<'\n';
    go(n-1,6-x-y,y);
}
 
void cnt(int n)
{
    string s="1";
    while(n--)
    {
        int up=0;
        for(int i=0;i<s.size();i++)
        {
            int d=(s[i]-'0')*2+up;
            if(d<10) s[i]=d+'0',up=0;
            else s[i]=d%10+'0',up=d/10;
        }
        if(up) s+=up+'0';
    }
    if(s[0]!='0') s[0]--;
    else
    {
        s[0]='9';
        for(int i=1;i<s.size();i++)
            if(s[i]!='0') { s[i]--; break; }
    }
    reverse(s.begin(),s.end());
    cout<<s<<'\n';
}
 
int main()
{
    int n;
    cin>>n;
    cnt(n);
    if(n<=20) go(n,1,3);
    return 0;
}