[백준] 11729번 하노이 탑 이동 순서

문제

---

https://www.acmicpc.net/problem/11729

풀이과정

---

하노이 탑의 이동 횟수를 구하는 문제다. 하노이 탑의 개념은 알고 있었지만 코드로 구현하는건 처음이라 신기했다.

분할 정복 문제라는 것을 알고 시작했지만 어떻게 해결해야될지 몰라서 조금 오래 걸린 것 같다. 답을 보는게 습관이 된 것 같다. 이제 한시간 안에 답을 보는건 그만 좀 해야겠다.

solve(n,x,y) 를 n개의 원판을 x->y 로 옮기는 함수라고 하고 재귀호출로 풀면 해결이 된다.

그리고 처음에는 원판을 옮길 때마다 횟수를 증가시켜서 마지막에 횟수를 출력했는데 검색을 해보니까 하노이 탑의 이동횟수에 대한 공식이 있었다.

그래서 pow() 함수를 통해서 출력을 했는데 틀렸습니다가 떠서 왜 그런가 살펴봤더니 N이 커질수록 double형으로 리턴해주는 pow() 함수는 모든 숫자를 표현할 수 없었다. 그래서 int로 형변환을 해주니까 맞았다고 떴다.

pow() 함수가 아니여도 시프트 연산자를 통해 제곱승을 표현할 수 있다.

풀면서 배운 점

---

1. 하노이 탑의 이동 횟수 구하는 공식 : 원판이 N개일 때, 2^N-1
2. pow()는 double형으로 리턴해주기 때문에 int형 답을 원할 경우 모든 경우를 표현할 수 없다.
3. << 는 왼쪽 시프트 연산자로 1<<3 이면 1을 왼쪽으로 세 칸 시프트 한 것이기 때문에 2^3=8이 된다.

소스코드

---

#include <iostream>
#include <cmath>

using namespace std;

int N;

void solve(int n, int x, int y)
{
    if (n == 0) return;

    solve(n - 1, x, 6 -x-y); // 6-x-y) : 2번째 장대
    cout << x << " " << y << "\n";
    solve(n - 1, 6 - x - y, y);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;

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

    solve(N, 1, 3);

    return 0;
}