C++ / 백준 / 11729 / 하노이 탑 이동 순서

문제

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

11729번: 하노이 탑 이동 순서

문제풀이

N=5일때 맨 아래 5번 원판을 세번째 장대로 옮겨야한다.

start를 시작 장대, end를 목표 장대, via를 start->end로 옮기기 위해 거치는 장대로 둔다.

5번 장대를 세번째 장대로 옮기기 위해서는 1~4번 원판을 2로 옮겨야 한다.

따라서 3번을 거쳐 2번으로 두기 때문에 hanoi(N, start, via, end)라는 함수가 있으면

hanoi(N-1, start, end, via)로 둔다.

4번 원판을 세번째 장대로 옮겨야한다.

4번 원판을 옮기기 위해서는 1~3 원판을 1로 옮겨야한다.

hanoi(N-1, via, start, end)로 둔다.

 

 

4번 원판을 세번째 장대로 옮긴다.

처음과 같은 형태가 됐다. 재귀 함수를 이용해서 반복을 한다.

N=1일때 시작장대에서 목표장대로 옮기므로 출력을 해준다.

 

 

코드

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

void hanoi(int N, char start, char via, char end) {
	if (N == 1) cout << start << ' ' << end << '\n';
	else
	{
		hanoi(N - 1, start, end, via);
		cout << start << ' ' << end << '\n';
		hanoi(N - 1, via, start, end);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N = 0;
	cin >> N;
	cout << (int)pow(2, N) - 1 << '\n';
	hanoi(N, '1', '2', '3');
}