#include <stdio.h> // printf()의 이용을 위한 헤더 파일 포함.
 
int count = 0; // 이동 횟수에 이용.
 
void Hanoi(char a, char b, char c, int n);
 
 
// 하노이 탑 재귀함수
void Hanoi(char from, char temp, char to, int n)
{
	if (n == 1){
		printf("1번 원반 %c에서 %c로 이동\n", from, to);
		count++;
	}
	else{
		Hanoi(from, to, temp, n - 1);
		printf("%d번 원반 %c에서 %c로 이동\n", n, from, to);
		count++;
		Hanoi(temp, from, to, n - 1);
	}
 
}
 
 
// main 함수 시작 
int main(void)
{
	int n; //원반의 수
	printf("\n * A탑에서 C탑으로 이동하며 총 3개(A, B, C)의 탑이있다.\n\n   옮기려는 원반의 수를 적고 엔터키를 치시오.--> ");
 
	scanf_s("%d", &n);
 
	Hanoi('A', 'B', 'C', n);    // 하노이 탑 재귀함수를 실행할 때 처음 from(시작점)을 A로 놓고
	// to(목적점)을 C로 놓고 시작한다.
	printf("\n\n   [ %d ] 개의 원반을 옮기려면 [ %d ] 번 이동해야합니다.\n\n", n, count);
	return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+IC8vIHByaW50Zigp7J2YIOydtOyaqeydhCDsnITtlZwg7Zek642UIO2MjOydvCDtj6ztlaguCgppbnQgY291bnQgPSAwOyAvLyDsnbTrj5kg7Zqf7IiY7JeQIOydtOyaqS4KCnZvaWQgSGFub2koY2hhciBhLCBjaGFyIGIsIGNoYXIgYywgaW50IG4pOwoKCi8vIO2VmOuFuOydtCDtg5Eg7J6s6reA7ZWo7IiYCnZvaWQgSGFub2koY2hhciBmcm9tLCBjaGFyIHRlbXAsIGNoYXIgdG8sIGludCBuKQp7CglpZiAobiA9PSAxKXsKCQlwcmludGYoIjHrsogg7JuQ67CYICVj7JeQ7IScICVj66GcIOydtOuPmVxuIiwgZnJvbSwgdG8pOwoJCWNvdW50Kys7Cgl9CgllbHNlewoJCUhhbm9pKGZyb20sIHRvLCB0ZW1wLCBuIC0gMSk7CgkJcHJpbnRmKCIlZOuyiCDsm5DrsJggJWPsl5DshJwgJWProZwg7J2064+ZXG4iLCBuLCBmcm9tLCB0byk7CgkJY291bnQrKzsKCQlIYW5vaSh0ZW1wLCBmcm9tLCB0bywgbiAtIDEpOwoJfQoKfQoKCi8vIG1haW4g7ZWo7IiYIOyLnOyekSAKaW50IG1haW4odm9pZCkKewoJaW50IG47IC8v7JuQ67CY7J2YIOyImAoJcHJpbnRmKCJcbiAqIEHtg5Hsl5DshJwgQ+2DkeycvOuhnCDsnbTrj5ntlZjrqbAg7LSdIDPqsJwoQSwgQiwgQynsnZgg7YOR7J207J6I64ukLlxuXG4gICDsmK7quLDroKTripQg7JuQ67CY7J2YIOyImOulvCDsoIHqs6Ag7JeU7YSw7YKk66W8IOy5mOyLnOyYpC4tLT4gIik7CgoJc2NhbmZfcygiJWQiLCAmbik7CgoJSGFub2koJ0EnLCAnQicsICdDJywgbik7ICAgIC8vIO2VmOuFuOydtCDtg5Eg7J6s6reA7ZWo7IiY66W8IOyLpO2Wie2VoCDrlYwg7LKY7J2MIGZyb20o7Iuc7J6R7KCQKeydhCBB66GcIOuGk+qzoAoJLy8gdG8o66qp7KCB7KCQKeydhCBD66GcIOuGk+qzoCDsi5zsnpHtlZzri6QuCglwcmludGYoIlxuXG4gICBbICVkIF0g6rCc7J2YIOybkOuwmOydhCDsmK7quLDroKTrqbQgWyAlZCBdIOuyiCDsnbTrj5ntlbTslbztlanri4jri6QuXG5cbiIsIG4sIGNvdW50KTsKCXJldHVybiAwOwp9