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

11729번 하노이 탑 이동 순서 문제다.

 

일단 답부터 올리면..

//#include <iostream>
//#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
using namespace std;
 
void hanoi(int from, int to, int size);
 
int main()
{
    int input, repeat;
    repeat = 0;
    //cin >> input;
    scanf("%d", &input);
    for (int i = 0; i < input; i++)
        repeat = repeat * 2 + 1;
 
    //cout << repeat << endl;
    printf("%d\n", repeat);
    hanoi(1, 3, input);
}
 
void hanoi(int from, int to, int size) {
    if (size > 1)
        hanoi(from, 6 - (from + to), size - 1);
    //cout << from << ' ' << to << endl;
    printf("%d %d\n", from, to);
    if (size > 1)
        hanoi(6 - (from + to), to, size - 1);
}

뭐 이렇게..

 

일단 규칙을 찾아보면 간단하다.

n층짜리 하노이의 탑을 3번째로 옮기려면 제일 큰 층을 뺀 나머지 n-1층을 통째로 2번째로 옮긴다.

그리고 덩그러니 남아있는 제일 큰 층을 3번째로 옮기고, n-1층을 3번째로 옮긴다.

 

또 여기서 자세히 보면 n-1층도 마찬가지로 n-2층을 통째로 1번째로 옮기고, 두 번째로 큰 층을 3번째로 옮긴다.

 

이와 같이 반복하면 된다.

 

이정도면 충분하겠지..하고 돌렸는데 이게 무슨.. 시간초과가 떴다..

 

여기서 더 줄일게 있나..? 아예 접근방법을 바꿔야하나..? 했는데 그러지 않아도 충분했다.

 

애초에 계산 자체는 금방 끝난다. 위 코드는 시간을 줄이기 위해 바로바로 출력하지만, 따로 실행하본 결과 계산한 내용을 list<pair<int, int>>에 저장한 후 출력해도 어느정도 수로는 금방 출력을 시작한다. 따라서 계산이 오래걸리는게 아니라 출력이 오래걸리는거다.

 

그래서 구글링을 해보니, cout, cin이 printf, scanf보다 느리다는것을 오랜만에 상기했다. 요즘 맨날 자바만 만져서..

 

그래서 cstdio을 넣고 printf, scanf로 바꿨더니 시간초과가 안걸렸다.