백준 11729 하노이 탑 이동순서 - 분할정복 -C++

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

11729번: 하노이 탑 이동 순서

사실 문제를 보고 꽤 고민을 해봤는데, 어떻게 푸는 문제인지 전혀 감이 잡히지 않았다.

아직 PS에 대한 감이 많이 부족한것 같다.

 

함수를 recursive하게 정의하는 부분에서 사고가 좀 막힌것 같다.

탑이 있는곳, 탑이 옮겨질 곳, 안쓰는 곳 세개로 함수를 구현한 다음에

옮길 함수의 탑 층수가 1일때만 옮기고, 1 이상일때는 층수를 하나 줄여서 재귀 구조로 짜면 된다.

 

#include <iostream>
using namespace std;
int answernum;
 
int Ans(int num){
    int answer=0;
    int i=1;
    while(i<=num){
        answer = 2*answer+1;
        i++;
    }
    return answer;
}
 
void hanoi(int num, int from, int to, int not_use){
    if(num==1)
        cout<<from<<" "<<to<<"\n";
    else{
        hanoi(num-1,from,not_use,to);
        hanoi(1,from,to,not_use);
        hanoi(num-1,not_use,to,from);
    }
}
 
int main(void){
    int num;
    cin>>num;
    cout<<Ans(num)<<"\n";
    hanoi(num,1,3,2);
 
}

아직 함수를 어떤 식으로 구현해야 하는지에 대한 감이 부족한것 같다. 연습만이 살길.