[백준] 11729 하노이 탑 이동순서 (C++)

분명 맞는데 시간초과만 나서 인터넷 검색했다가 이마 팍팍 때린 문제... 결론은 로직은 맞았고 입출력이 문제였다.

원인은 프로그래머스만 푸느라 입출력에는 신경을 써본 일이 없어서 cout이 얼마나 느린 입출력이었는지 까먹고 있었다는거였다. 후... 다음부턴 출력을 많이 해야하는 문제는 무조건 printf 를 써야지... 

 

문제 설명

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

문제 풀이

워낙 유명한 문제니까 풀이는 패스

#include <queue>
#include <iostream>
using namespace std;

void hanoi(int n, int now, int toward, int empty)
{
    if (n == 1) printf("%d %d\n", now, toward);
    else {
        hanoi(n - 1, now, empty, toward); // 위에 쌓인 원판을 잉여자리로 이동
        printf("%d %d\n", now, toward); // 맨 밑 원판을 목표 위치로 이동
        hanoi(n - 1, empty, toward, now); // 나머지 원판을 목표위치로 이동
    }
}

int main()
{
    int N, answer=1;
    cin >> N;

    for (int i = 1; i < N; i++) answer = 2 * answer + 1;
    
    cout << answer << endl;
    hanoi(N, 1, 3, 2);

}