[BOJ] 백준 11729번 : 하노이 타워 이동순서 : 아주정은

하노이 타워는 컴퓨터 프로그래밍 시간에 예제로 배웠었다.

또한, 자료구조시간에도 배웠다. 그래서 이동 방법을 구현하는데는 큰문제는 없었다.

그치만 계속 문제가 발생했다. 시간초과가 뜨는것이다.

아마도

ios::sync_with_stdio(false);

cin.tie(0);

를 쓰지 않아서 그런것같다.

저거를 쓰기전에 scanf printf로 해보았는데, 잘 됐다.

앞으로는 꼭 써주자. 그리고 endl 도 쓰지 말라대? 암튼 앞으로 "\n"를 사용하도록 하지.

하노이 타워는 n개의 탑을 1에서 3으로 이동시킬려면, 1에서 2로 n-1개를 옮기고 n번째 돌(?)을 1에서 3으로 옮긴다. 그리고 n-1개를 2에서 3으로 옮기면 된다.

이걸 재귀로 부르면 된다.

구웃~!

#include<stdio.h>
#include<iostream>

using namespace std;

void print(int a, int c) {
	cout<<a<<" "<<c<<"\n";
}

void hanoi(int n, int a, int b, int c) {
	if (n == 1) {
		print(a, c);
	}
	else {
		hanoi(n - 1, a, c, b);
		print(a, c);
		hanoi(n - 1, b, a, c);
	}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
	int N, a = 1;
	cin>>N;
	for (int i = 0; i < N; i++) {
		a *= 2;
	}
	cout<<a-1<<"\n";
	hanoi(N, 1, 2, 3);

}