백준 1914 하노이 탑 (C++)

안유태·2023년 9월 26일
0

알고리즘

목록 보기
150/239

1914번: 하노이 탑

기본적인 알고리즘인 하노이 탑을 구현하는 문제이다. 하노이 탑을 구현하는 것은 간단하게 할 수 있었지만 옮긴 횟수를 구할 때 신경을 써야한다. 문제에서 n의 최댓값이 100이기 때문에 단순히 int로 구한다면 실패를 하게된다. 문자열을 이용해서 옮긴 횟루를 구해주어야 한다. 어렵지 않게 풀 수 있었다.



#include <iostream>
#include <cmath>
#include <string>

using namespace std;

int N;
string result;

void hanoi(int start, int tmp, int end, int n) {
    if (n == 1) {
        cout << start << " " << end << "\n";
        return;
    }

    hanoi(start, end, tmp, n - 1);
    cout << start << " " << end << "\n";
    hanoi(tmp, start, end, n - 1);
}

void solution() {
    result = to_string(pow(2, N));
    result = result.substr(0, result.find('.'));
    result[result.size() - 1] -= 1;

    cout << result << "\n";
    if (N <= 20) {
        hanoi(1, 2, 3, N);
    }
}

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

    cin >> N;

    solution();

    return 0;
}
profile
공부하는 개발자

0개의 댓글