[프로그래머스] 하노이의 탑

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12946

알고리즘 접근 방법

재귀 -> 여기까진 생각해냈다.. ㅎ
근데 어떻게?

• 1->2 : n-1개의 원판을 옮긴다. 1에는 가장 큰 n번째 원판만 남게 된다.
• 1->3 : 가장 큰 n번째 원판을 옮긴다.
• 2->3 : n-1개의 원판을 옮긴다.

풀이

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> answer;

void Hanoi(int start, int mid, int dest, int n)
{
    if (n == 0)
        return;
    
    Hanoi(start, dest, mid, n-1);
    answer.push_back({start, dest});
    Hanoi(mid, start, dest, n-1);
}

vector<vector<int>> solution(int n) {
    
    // 1->2 : n-1개의 원판을 옮긴다. 1에는 가장 큰 n번째 원판만 남게 된다.
    // 1->3 : 가장 큰 n번째 원판을 옮긴다.
    // 2->3 : n-1개의 원판을 옮긴다.
    
    Hanoi(1, 2, 3, n);
    
    return answer;
}

참고 블로그

(C++) - 프로그래머스(연습문제) : 하노이의 탑