삼성전자 알고리즘/정올
2. 1161 : 하노이탑1
기명준
2019. 5. 9. 22:09
문제 출처 : http://bitly.kr/b0EzMQ
정올::Xpert
하노이의 탑에 대한 전설은 아래와 같다. 고대 인도의 베나레스(현재 베트남의 하노이)에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 기둥이 동판 위에 세워져 있다. 기둥 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓여 있다. 이것은 신성한 브라흐마의 탑이다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 기둥으
www.jungol.co.kr
/**************************************************************
Problem: 1161
User: hbrojun.kim
Language: C++
Result: Success
Time:11 ms
Memory:1740 kb
****************************************************************/
#include <iostream>
using namespace std;
//https://cafe.naver.com/cafec/156013
//하노이탑 함수(원반의 개수, 시작봉, 목적봉, 중심봉)
//{
// if (원반의 개수 == 1){
// 장애물 치우기(시작봉 -> 중심봉)
// }
// else{
// n-1원반을 시작봉->중심봉으로 이동을 예정한다.
// n 원반을 시작봉->목적봉 이동
// n-1 원반을 중심봉->목정봉으로 이동을 예정한다.
// }
//}
void hanoi(int n, int a, int b, int c){
if (n == 1){
printf("%d : %d -> %d\n", n, a, b);
}
else{
hanoi(n - 1, a, c, b);
printf("%d : %d -> %d\n", n, a, b);
hanoi(n - 1, c, b, a);
}
}
int main(){
//recursive 문제
int n;
scanf("%d", &n);
hanoi(n,1,3,2); //1,3,2
return 0;
}