[분할정복]1914번 하노이의 탑(C++)

 

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

 

나는 바보야

나는 문어야

이문제 혼자서 막 dfs 이런걸로 풀려하다가

도저히 못풀겠어서 답지 펼쳐봄

 

하...

 

근데 알고나면 이해하기 쉽고 뭔가 새록새록 재밌었쌈!

 

 

 

 

 

#include <iostream>

#include <cmath>

using namespace std;

void result(int from, int by, int to, int n)

{

    if (n == 1)

        cout << from << " " << to << "\n";

    else

    {

        result(from, to, by, n - 1); // n-1의 위치 (중간에 있어야, n이 마지막으로감)

        cout << from << " " << to << "\n";

        result(by, from, to, n - 1); // 이제 n위에 n-1이 올라가야함

    }

}

int main()

{

    int n;

    cin >> n;

    long k = pow(2, n) - 1;

    cout << k << "\n";

    result(1, 2, 3, n);

}

여기서 재귀 함수 자체를 "옮기는 행위" 라고 보면 됨

 

결국 원하는건

1번째 발판에 있는 크기 n 고리를 3번째로 옮기고 싶은거잔아

근데 그걸 하려면

그 위로 n-1개가 2번째에 있어야 한다

어 근데 그걸 또 하려면 n-2가 3번째에.... 이걸 반복하는 건데

 

처음엔 이해가 잘 안갈수있어

나도 그랬거든

한 1시간동안 영상보면서 복습하니까 이해됨~꿌꿌