Today's Algorithm(2018-10-05)

boj 1914

오늘 알고리즘은 오전에 배운 '하노이탑'을 설명해보려고 했는데요. 이게 어떻게 구현할 수 있는지는 배웠지만 막상 설명하려고 생각하니 정말 감이 안잡히네요. 아직 재귀가 익숙하지 않은 것 같아요. 그래도 제가 좀 더 성장하였을 때 제대로 설명할 수 있을거라 생각하며 honux가 설명한 코드를 남겨놓으려 합니다.

#include <iostream>
#include <cmath>
int count = 0;
int limit;

void move(int n, int src, int target) {
    printf("%d %d\n", src, target);
}

void hanoi(int n, int fr, int to) {
    count++;
    if(n == 1) {
        move(n, fr, to);
        return;
    }

    int other = 6 - fr - to;
    hanoi(n-1, fr, other);
    move(n, fr, to);
    hanoi(n-1, other, to);
}

int main() {
    long double input;
    scanf("%Lf", &input);
    limit = input;
    printf("%0.0Lf\n", (long double)pow(2, input));
    if(limit <= 20) {
        hanoi(input, 1, 3);
    }
}

이 코드를 백준 온라인 저지에 제출을 하니 자꾸 실패가 떴었는데요. 그 이유를 알아보니 입력값이 클 경우 결과값을 제대로 출력을 못하더라구요. Int의 범위를 벗어나는 경우 BigInteger를 직접 구현해야 한다고 하는데 인터넷에서 구현하는 과정을 살펴보니 정말 어려운 것 같아요. 이 부분도 알고리즘 문제를 풀면서 해결해나가야할 숙제 같아요.

 

오늘 '하노이탑'을 구현하려다 시간이 다 갔네요. 어제 풀었던 '별찍기-11'을 재귀로 리팩토링 해보고 풀이과정에 대해서도 써보고 싶었는데 아쉽습니다. 내일 기회가 되면 설명하도록 하겠습니다!!