[c++] 백준 11729 - 하노이 탑 이동 순서 [구현?재귀?]

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

---

머리좀 식힐라고 간만에 실버문제를 풀었다.

하노이의 탑 진짜 너무 오랫만에 봐서 기억은 안났고 생각해내야 했다.

 

우선 천천히 하노이의 탑을 쌓아보았다.

ㅋㅋㅋㅋ진짜 이러고 있었음

 

3짜리 두번정도 쌓아보니까 나온 점화식은 다음과 같다.

Hanoi(N) = Hanoi(N-1) + 1 + Hanoi(N-1)

 

하노이를 옮기는것은

하노이탑보다 하나 작은 탑을 1에서 2로 옮긴 다음에에에1에서 3으로 한개를 옮기고2에서 3으로 하나 작은 탑을 옮기면 됨

그런데 문제 보니까 순서대로 적어야 되더라고....

그래서 내가 생각한 식은

A~B로 사이즈 N짜리 탑을 옮겨야 한다!

이다.

 

따라서 Hanoi(int from, int to, int val) 을 만드는걸 목표로 하고

위 식과 똑같이 해주면 됬다.

1일때는 printf를 해주고

 

그리고 괜히 vector<pair<int,int>> 이런거에 저장해두면 메모리 터질거 같아서 그냥 함수 두개 만들어서 때려넣었다.

 

next함수는 1,2,3중 from,to에 없는 수를 반환하는 함수다.

#include <bits/stdc++.h>
using namespace std;
int answer = 0;
int next(int a,int b){
    bool t[4]={false,}; t[a] = true; t[b] = true;
    for(int i=1;i<=3;i++){if(!t[i]) return i;}
    return -1;
}
int hanoi_calcul(int from,int to,int val){
    if(val == 1){return 1;}
    else{return hanoi_calcul(from,next(from,to),val-1) + 1 + hanoi_calcul(next(from,to),to,val-1);}
}

void hanoi_show(int from, int to, int val){
    if(val == 1){printf("%d %d\n",from,to);}
    else{
        hanoi_show(from ,next(from,to),val-1 );
        printf("%d %d\n",from,to); 
        hanoi_show(next(from,to),to,val-1);
    }
}

int main(){
    int N; cin>>N;
    printf("%d\n",hanoi_calcul(1,3,N));
    hanoi_show(1,3,N);
}