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

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

1914번: 하노이 탑

이 문제의 로직은 기존 하노이탑과 동일합니다. 그런데 원판의 개수가 100개라서 최악의 경우 O(2^100)이 걸리기 때문에, 이는 기존 int형, long형의 범위를 훨씬 초과하게 됩니다.

 

기존 하노이탑 로직 예시(그림에서 원판이 n = 5개인 경우)

1. 4(n-1)개의 원판(가장 아래쪽의 있는 원판을 제외한 나머지 원판)을 2번 탑으로 이동시키기
2. 1개의 원판(가장 아래쪽에 있는 원판)을 3번 탑으로 이동시키기 
3. 그 외 4(n-1)개의 원판 2번 탑 -> 3번 탑으로 이동

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>

using namespace std;

void hanoi(int n, int a, int b, int c)
{
    if (n == 1)
    {
        printf("%d %d\n", a, c);
    }
    else
    {
        hanoi(n - 1, a, c, b);
        printf("%d %d\n", a, c);
        hanoi(n - 1, b, a, c);
    }
}
int main(void)
{
    int n;
    scanf("%d", &n);
    string count;
    count = to_string(pow(2, n));
    int idx = count.find('.');
    count = count.substr(0, idx);
    count[count.length() - 1] -= 1;

    cout << count << '\n';

    int a = 1;
    int b = 2;
    int c = 3;
    if (n <= 20)
        hanoi(n, a, b, c);
}

핵심 부분은 count부터이다. count에서 2^n을 string으로 파싱해줘야 합니다. 왜냐하면 길이가 엄청 길 것이고, int형의 범위로는 나타내는데 한계가 있기 때문입니다. 그리고 소수부가 나오기 전까지 idx를 확인해 주고, 정수부만 나타내주면 됩니다. 더불어 마지막에 -1을 해주는 이유는 하노이탑의 횟수 공식은 2^n - 1이기 때문입니다.