[백준 - C++] 11729번: 하노이 탑 이동 순서

알고리즘에서 엄청나게 유명한 하노이의 탑 문제이다. 

엄청나게 유명한 것에 비해서 난이도가...그렇게 높진 않고 랭크도 높아서 조금 의아.

암튼 입력과 출력은 이래야 된다.

구현은 C++로 해보았다.

재귀함수 형식으로 구현하면 쉽게 풀린다.

#include <iostream>
#include <cmath>
using namespace std;


void HanoiTower(int num, int from, int by, int to){	//from에 있던 num개의 원반을 by를 거쳐 to로 이동시키는 함수
    
    if (num == 1){	//이동해야 할 원반의 수가 1개인 경우 그냥 옮기면 됨. 그리고 탈출 조건이 됨.
        printf("%d %d\n", from, to);
    }
    else{
        HanoiTower(num-1, from, to, by);	
        printf("%d %d\n", from, to);
        HanoiTower(num-1, by, from, to);
    }
}

int main(void){
    int N;
    scanf("%d", &N);
    printf("%d\n", static_cast<int>(pow(2, N)) - 1);
    HanoiTower(N, 1, 2, 3);
    
    return 0;
}

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

11729번: 하노이 탑 이동 순서

참고 자료 : "윤성우의 열혈 자료구조" - 윤성우 저