백준/11729번(하노이타워 재귀)/C

문제 설명

입출력 조건

 

재귀함수 구현 연습을 해볼 수 있는 간단한 문제

 

#include <stdio.h>
#include <math.h>

void hanoi_rec(int from, int mid, int to, int x) {		//하노이 함수
	if (x == 1) {
		printf("%d %d\n", from, to);
	}

	else {
		hanoi_rec(from, to, mid, x - 1);
		printf("%d %d\n", from, to);
		hanoi_rec(mid, from, to, x - 1);
	}
}

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

	int execution;
	execution = pow(2, n) - 1;		//시행 횟수 출력
	printf("%d\n", execution);

	hanoi_rec(1, 2, 3, n);
}

 

 

디버깅 기록

: 처음에는 시행횟수를 계산할 때, 정직하게 시행횟수를 세는 전역변수를 추가해서 printf문 앞에서 매번 1씩 증가시켜주는 식으로 구현을 했다. 그런 방법으로는 도저히 시행횟수만을 먼저 출력하는 게  불가했는데, 시행횟수를 구할 때는 꼭 실제로 셀 필요는 없다는 걸 깨닫았다. 차수표현법으로 시행횟수를 계산할 수 있다는 점을 염두에 두자.