재귀 - 11729번

1월 10일(화) - 재귀                          (11729번)

11729번: 하노이 탑 이동 순서

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. 하노이 함수 및 그에따른 재귀는 자료구조 복습중에도 다시 해본 내용이라서 쉬웠지만, k 카운팅을 하나하나 해보려다가 실패했다

-> 결국 입력된 n 값을 이용해서 (2^n - 1) 을 k 값으로 활용했다.

-> k 값을 재귀 안에서 직접 카운팅 하는 것이 가능한것인지 더 알아봐야할 것 같다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

void hanoi(int n, int start, int path, int end)
{
	if (n == 1)
	{
		printf("%d %d\n", start, end);
	}
	else
	{
		hanoi(n - 1, start, end, path);
		printf("%d %d\n", start, end);
		hanoi(n - 1, path, start, end);
	}
}

int main(void)
{
	int n;
	scanf("%d", &n);

	int k = 1;
	for (int i = 0; i < n; i++)
	{
		k = k * 2;
	}

	printf("%d\n", k - 1);
	hanoi(n, 1, 2, 3);		

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ