Week 3 (재귀) - 문제 1914번 (하노이 탑)

문제:

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

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

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

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

 

입력:

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.

 

출력:

첫째 줄에 옮긴 횟수 K를 출력한다.

N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

 

예제 입력1:

3

예제 출력1:

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

코드:

#include <iostream>
#include <cmath>
#include <string>

using namespace std;

void rst_1(int N_,int one, int two, int three)		//옮기는 알고리즘 구현
{
	if (N_ > 20)
		return;
	if (N_ == 1)
	{
		cout << one << " " << three << "\n";
		return;
	}
	else
	{
		rst_1(N_ - 1, one, three, two);
		cout << one << " " << three << "\n";
		rst_1(N_ - 1, two, one, three);
		return;
	}

	//N개의 원판을 옮기기 위해선,
	//N-1번째 단계의 과정들에서 2화 3이 바뀐 것 실행 후,
	//맨 밑 가장 큰 원판 옮기는 과정 1 3이 실행한 뒤에,
	//다시 N-1번쨰 단계의 과정들 중에서 1과 2가 바뀌어서 실행이 된다.
}

int main()
{
	iostream::sync_with_stdio;			//입출력 빨라지는 것
	cin.tie(0);
	cout.tie(0);

	int N;								//N선언과 입력받기
	cin >> N;
	
	string a = to_string(pow(2, N));

	//pow는 double 형을 빼준다. pow를 쓰는 이유는
	//2의 100제곱은 숫자가 크기 때문에
	//int의 범위를 고려하고 double을 이용하여 문제를 풀 것이다.
	//참고로 하노이탑 최소 실행 횟수는 2^(단계)-1이다.

	int x = a.find('.');				//pow 함수 결과가 실수형이기에 소수점 찾기
	a = a.substr(0, x);				//소수점 앞자리만 나오게하기
	a[a.length() - 1] -= 1;				//string a에 대한 마지막 위치의 인덱스 값에 -1

	cout << a << endl;

	rst_1(N, 1, 2, 3);

	return 0;
}

설명:

주석 참고