[알고리즘]하노이 탑

백준문제 1914번 하노이탑

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

이 문제를 풀때 생각해야 할 부분

• 재귀함수를 사용해서 하노이탑 구현하기
• 2의 100제곱까지의 값을 구해야 하는데 unsigned long long을 사용해서는 불가능하기 때문에 다른방식으로 값을 출력할 방법을 찾아야함

#include <stdio.h>
#include <string.h>

void run(int from, int to, int temp, int n);

int main(void) {

    char str[32]; // 2의 100제곱이 31자리의 수이기때문에 char배열의 길이를 32로해줌 > 마지막칸에는 null이 들어가야하기때문에
    int N, numlen; // N은 하노이탑을 몇개쌓을건지 담을 변수, numlen은 str의 길이를 담을 변수
    long double count = 1; // count에 이동이 총 몇번 발생하는지 저장

    scanf("%d", &N);
    
    //count 출력부분----------------------------
    for (int i = 0; i < N; i++) {
        count *= 2;
    }
    
    sprintf(str, "%.0Lf", count); // count에 담긴 수들을 char배열에 하나씩 넣어줌
    numlen = strlen(str); // char배열의 길이를 numlen에 저장
    str[numlen - 1] = (char)((int)(str[numlen - 1]) - 1); // str의 마지막에 담긴 숫자에서 1을 뺀다 > str자체가 char배열이기때문에 1을빼기위해 형변환을 해줌
    printf("%s\n", str);
    //count 출력부분----------------------------
    
    
    // 20이하의 N에대해 값의 이동을 출력한다
    if (N <= 20) {
        run(1, 3, 2, N);
    }
    
    return 0;
}



void run(int from, int to, int temp, int n) {
    if (n == 0) {
        return;
    }

    run(from, temp, to, n - 1); // from에 있는 값들을 to, temp에 순차적으로 보냄
    printf("%d %d\n", from, to);
    run(temp, to, from, n - 1); // 부모 함수의 n이 이동하기전에 n이 가야할곳을 비워줌
}