11729번: 하노이 탑 이동 순서(백준 C++)

11729번: 하노이 탑 이동 순서 링크

코드

#include <iostream>
#include <math.h>
using namespace std;

void hanoi(int n, int start, int mid, int end){
  if(n == 1)
    cout << start << " " << end << "\n";
  else{
    hanoi(n - 1, start, end, mid);
    hanoi(1, start, mid, end);
    hanoi(n - 1, mid, start, end);
  }
}
int main(){
  int n;
  cin >> n;
  cout << (1<<n) - 1 << "\n";
  hanoi(n, 1, 2, 3);
}

사견

1학년 때 막 재귀함수의 존재라는 걸 처음 배웠는데,
그 때 이 하노이탑의 최소 이동 수를 재귀로 작성하는 걸 했었었다.
이동수는 간단했다. n-1 개일때의 이동수 * 2 + 1 하면 됐으니까

근데 수업의 마지막에 교수님이, 한 번 이동하는 순서에 대한 코드작성을 생각해보라 하셨었다.
당시 의문의 자신감에 차 있던 나로써는 당당하게 머리를 굴려봤지만 그때의 나는 정답의 발치에도 못 갔던 기억이 난다.

그랬는데, 3년이 지난 지금 이렇게 문제로 만나 풀게 되었다.

근데 생각보다 쉽게 풀려서 당황스러웠다.

그때보다 조금은 더 나은 컴퓨팅적인 사고를 하게 되었나 싶다.

이 문제 해결의 핵심.

이렇게 되어있다.

위의 4단계를 반복하면 되는것이다.

이에 대한 코드는 아래와 같다.

void hanoi(int n, int start, int mid, int end){
  if(n == 1)
    cout << start << " " << end << "\n";
  else{
    hanoi(n - 1, start, end, mid);
    hanoi(1, start, mid, end);
    hanoi(n - 1, mid, start, end);
  }
}

이는 하노이탑 이동수도 엿볼수 있다.

보면 (n-1)개의 하노이탑을

A 에서 B
B 에서 C

이렇게 2번 옮기며

바닥, 1개의 하노이탑을

A에서 C
1 번 옮긴다.

그렇기 때문에 N개의 하노이탑의 이동 최소횟수가
(n-1)개 하노이탑 움직이는 수 * 2 + 1 이되는것이다.

그렇되면 횟수가

1 3 7 15 ...

이렇게 증가하게 되는데 이는 2^n - 1 과 같다.

그래서 Pow() 함수를 사용했는데...

계속 오답이라고 나왔다. 처음에는 아무리 생각해도 로직자체에는 이상이 없어서 당황했다.
해서 나중에 찾아보니 Pow가 문제였다.

Pow가 double형을 return 해서 int형의 출력을 받아야 하는 경우에는 오답처리가 된다고 한다..

그래서 pow 대신 shift 연산자를 사용해 주었다. 어차피 2의 제곱수니까.

cout << (1<<n) - 1 << "\n";

로직보다 pow때문에 더 공부하고 간 문제였다...