[Jungol] 정올 1161 하노이1

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=441&sca=2070

 Input 
3

 Output 

1 : 1 -> 3

2 : 1 -> 2

1 : 3 -> 2

3 : 1 -> 3

1 : 2 -> 1

2 : 2 -> 3

1 : 1 -> 3

▶ hanoi(원판 수, 시작 기둥 번호, 도착 기둥 번호)

 

hanoi(3, 1, 3)으로 3번 기둥의 바닥에 3번 원판이 놓여야 하므로

1, 2번 원판을 2번 기둥으로 옮겨야 한다.

 

결과적으로 3번 원판이 없다고 생각하면, hanoi(2, 1, 2)로 나타낼 수 있다.

즉, 도착 기둥번호가 3번이 아닌 2번으로 하면서 원판 개수도 2개인 문제와 같다.

 

위의 작업이 끝나서 1, 2번 원판이 두번째 기둥에 있다고 했을 때,

3번 원판을 세번째 기둥에 옮길 수 있다.

 

이제는 1, 2번 원판을 원래의 도착점인 3번으로 옮기면 된다. → hanoi(2, 2, 3)

결과적으로 시작 기둥 번호만 달라진 원판이 2개인 문제와 같은 문제이다.

---

#include <iostream>
using namespace std;
 
void hanoi(int n, int from, int other, int to) {
    if (n == 0) {
        return;
    }
 
    hanoi(n - 1, from, to, other);
    printf("%d : %d -> %d\n", n, from, to);
    hanoi(n - 1, other, from, to);
}
 
int main(void) {
    int n; cin >> n;
    hanoi(n, 1, 2, 3);  
}