mminky's

* 문제
https://www.acmicpc.net/problem/11729

[ 해결 원리 ]
하노이탑 개념에 대해 그림으로 쉽게 설명해두었으니 참고하면 좋을 것 같다 :)
https://mminky.tistory.com/116

[ 코드 ]
**하노이탑 파이썬 - 시간초과가 떴다면**
print(count) 대신 print(2**n - 1) 를 해라!
-> 하노이탑의 총 옮긴 횟수는 2^n - 1으로 정해져 있다.
(하지만 개인적으로 옮길 때 마다 count를 증가시켜서 총 count를 출력하는 게 맞다고 생각한다.
근데 그렇게 하면 시간 초과가 된다..)

import sys input=sys.stdin.readline n = int(input()) #count = 0 #옮긴 횟수 #ans='' def hanoi(disk_num,from_peg,to_peg,tmp_peg): global count,ans if(disk_num==1): print(from_peg,to_peg) # ans += '{} {}\n'.format(from_peg,to_peg) # count += 1 return hanoi(disk_num-1,from_peg,tmp_peg,to_peg) print(from_peg,to_peg) # ans += '{} {}\n'.format(from_peg, to_peg) # count += 1 hanoi(disk_num-1,tmp_peg,to_peg,from_peg) print(2**n - 1) #count를 하니 시간 초과 뜸 # (처음)1 에서 (최종)3으로 이동함 # 2는 거치는 곳일 뿐! hanoi(n,'1','3','2') #print(count) #print(ans)

[ 결과 ]
와.. 진짜 시간초과 너무한거 아니냐고....
몇 번을 시도해서 결국 통과되었다.. 너무해..

[ 문제 ]

Write a divide-and-conquer algorithm for the Towers of Hanoi problem. The Towers of Hanoi problem consists of three pegs and disks of different sizes. The object is to move the disks that are stacked, in decreasing order of their size, on one of the three pegs to a new peg using the third one as a temporary peg. The problem should be solved according to the following rules: 1 when a disk is moved, it must be placed on one of the three pegs; 2 only one disk may be moved at a time, and it must be the top disk on one of the pegs; and 3 a larger disk may never be placed on top of a smaller disk. (a) Show for your algorithm that . Here denotes the number of steps (moves), given an input of disks.)

[ 해결 코드 ]

#include<stdio.h>
int count = 0;
int hanoi(int disk_num, char from_peg, char to_peg, char tmp_peg) {
	if (disk_num == 1) {
		printf("Move disk#1 from %c to %c \n",from_peg, to_peg);
		count++;
		return;
	}
	hanoi(disk_num - 1, from_peg, tmp_peg, to_peg);//한  번에 한개(1)씩 옮김
	printf("Move disk#%d from %c to %c \n", disk_num,from_peg, to_peg);
	count++;
	hanoi(disk_num - 1, tmp_peg, to_peg, from_peg);

}
int main()
{
	int n = 3;
	int result;
	result = hanoi(n, 'A', 'C', 'B');
	printf("%d", result);
	return 0;
}

[ 결과 ]

n=3 이므로 2^3 - 1 = 7

총 7번이 실행된다.

[ 해결 아이디어 ]

[ 참고 사이트 ]

www.geeksforgeeks.org/c-program-for-tower-of-hanoi/