[#11729] 하노이 탑 이동 순서

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <math.h>
#include <stdio.h>
 
using namespace std;
 
//from에서 by를 이용하여 to로 옮긴다
void hanoi(int k, int from, int by, int to);
void move(int from, int to);
 
int main() {
    int k;
    scanf("%d", &k);
 
    cout << ((int)pow(2, k)) - 1 << endl;
    
    hanoi(k, 1, 2, 3);
 
    return 0;
}
 
void hanoi(int k, int from, int by, int to) {
    if (k == 1)
        move(from, to);
    else {
        hanoi(k - 1, from, to, by);
        move(from, to);
        hanoi(k - 1, by, from, to);
    }
}
 
void move(int from, int to) {
    printf("%d %d\n", from, to);
}
 

여러가지로 오래걸렸던 문제 ㅠㅠ

 

일단 하노이탑의 최소 이동 횟수 = 2의 N승 - 1      Ex) N=3이면 7

 

하노이탑의 원리는

N개의 원반을 기둥1에서 기둥 3으로 옮기기 (기둥 2를 이용)

1) N-1개의 원반을 기둥1에서 기둥2로 옮기기 (기둥 3을 이용)

2) 기둥 1에 남은 원반을 기둥 3으로 옮기기 

3) N-1개의 원반을 기둥2에서 기둥 3으로 옮기기 (기둥 1을 이용)

 

그리고 N이 1이면 그냥 from에서 to로 옮기면 된다.

 

hanoi(int N, int from, int by, int to): N개의 원반을 from에서 to로 옮기기 (by 이용) 재귀적으로 호출하기

 

채점을 했는데 시간 초과....

찾아보니까 N이 크면 출력이 많아서 cout을 쓰면 시간 초과가 난다고 해서 printf로 다 고침

cout을 고치니까 cin이 보기싫어서 scanf로 고침

visual studio에서 실행이 안되길래 scanf_s로 고쳤더니 채점할때 컴파일 오류나서 다시 scanf로 고치고 첫부분에#define _CRT_SECURE_NO_WARNINGS 추가

 

또 채점을 했는데 오답....

찾아보니까 pow 반환형이 double이라서 오답이 난다고 하길래 명시적으로 형변환 해줬더니 드디어 정답!!