[BOJ / 백준] 11729번 하노이 탑 이동 순서 C++ 문제 풀이

단계별로 풀어보기 - 재귀 단계 - [4단계] 11729번

문제

문제 링크 : www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

입력 복사 : 

3

 

 

CODE

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

void hanoi(int start, int mid, int end, int n) {
	if (n == 1) {
		cout << start << " " << end<< "\n";
	}
	else {
		hanoi(start, end, mid, n - 1);
		cout << start << " " << end << "\n";
		hanoi(mid, start, end, n - 1);
	}
}

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

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

 

 

풀이

n개의 원판을 첫번째 막대에서 세번째 막대로 옮기는 기본적인 방법은

n-1개의 원판을 첫번째에서 두번째로,

마지막 원판을 첫번째에서 세번째로,

n-1개의 원판을 두번째에서 세번째로 옮기는 것이다.

이를 바탕으로 재귀 함수를 작성하였다.

 

또한, 옮긴 횟수는 출력하는 한줄마다 count하면 좋겠지만,

횟수를 먼저 출력해야하므로

하노이탑 최소 이동횟수 2^n - 1을 계산하여 출력하였다.

 

	cout << (int)pow(2, n) - 1 << '\n';

여기서 pow 함수 앞에 (int)를 적지 않으면,

입력 최대가 20인 pow 함수의 특성상 오차가 커져서 '틀렸습니다.'가 뜹니다!

 

 

 

결과