하노이의 탑

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

1914번: 하노이 탑

void recur(int from, int to, int bypass, int n) 
{
    if (n == 1) // 옮길게 한개면 그냥 그대로 옮기면됨.
    {
        cout << from << ' ' << to << '\n';
    }
    else 
    {
        recur(from, bypass, to, n - 1);
        cout << from << ' ' << to << '\n';
        recur(bypass, to, from, n - 1);
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
 
    cin >> n;
 
    string minNum = to_string(pow(2, n));
    minNum = minNum.substr(0, minNum.find('.'));
    minNum[minNum.size() - 1] -= 1;
 
    cout << minNum << endl;
 
    if (n <= 20)
        recur(1, 3, 2, n); // 1번부터 3번까지 2번을 이용해서 n개를 옮길것이다.
 
    return 0;
}

 

이런 DP같은 느낌의 문제들은 큰 그림(?)을 잘 생각해야 한다. 

 

일단 문제의 목적은 1번기둥에 크기순으로 쌓여있는 원판들을 그대로 3번으로 옮기는게 목표이다.

 

그리고 어떠한 경우에도 원판은 크기순으로 쌓여있어야한다.

 

이런 재귀문제를 풀때는 1번기둥 2번기둥, 3번기둥 이런것에 생각이 매몰되면 안되고 그냥 

 

'이 기둥에서 저 기둥으로 옮기려면?' 으로 일단 목적자체를 심플하게 설정해야한다.

 

 

특정기둥A에서 특정기둥B로 원판을 옮기려한다고 생각하자. 

 

그러면 A기둥의 가장 큰 원판인, 가장 밑에있는 원판을 B기둥으로 옮겨야한다. (그대로 옮겨야하니까)

 

그럴려면 가장 아래에있는 1개의 큰원판을 B기둥으로 옮기기 위해, n-1개의 원판을 다른 기둥(C기둥)에 옮겨야한다.

위에것들을 치워놔야 가장 밑바닥의 큰원판을 옮길 수 있기 때문이다.

 

그러면 다시 임시로 옮겨놨던 n-1개의 C기둥의 원판들을 A기둥을 거쳐 B로 옮기면 된다.

 

여기까지가 한 사이클이다. 여기까지의 내용이 결국 특정기둥에서 특정기둥까지의 이동에 대한 내용이다.

그리고 이 로직 그대로 내용에 있는 '?기둥에서 ?기둥까지 옮긴다..'라는 곳에 적용해주면 된다.