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

11729번: 하노이 탑 이동 순서

하노이 알고리즘 알고리즘 구현 문제이다. 하노이 알고리즘은 워낙 유명하기 때문에 어렵지 않게 풀 수 있었다. 문제 제출 시에 시간 초과와 실패를 했는데 두가지 이유가 있었다.

• endl은 "\n"보다 시간이 오래 걸린다. 참고
• cmath의 pow는 double형을 리턴하기 때문에 6자리가 넘어가면 지수 표기가 적용된다. (int)로 형변환을 해주어야 한다. 참고

#include <iostream>
#include <cmath>

using namespace std;

int N;

void hanoi(int n, int from, int tmp, int to) {
    if (n == 1) {
        cout << from << " " << to << "\n";
        return;
    }
    else {
        hanoi(n - 1, from, to, tmp);
        cout << from << " " << to << "\n";
        hanoi(n - 1, tmp, from, to);
    }
}

void solution() {
    cout << (int)pow(2, N) - 1 << "\n";
    hanoi(N, 1, 2, 3);
}

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

    cin >> N;

    solution();

    return 0;
}