[BOJ][11729] 하노이 탑 이동 순서

1. 문제 링크

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

2. 사용 알고리즘

분할정복

3. 풀이

1번~5번 원판을 1 -> 3으로 이동하는 경우

1) 1번~4번 원판을 1 -> 2로 이동

2) 5번 원판을 1 -> 3으로 이동

3) 1번~4번 원판을 2 -> 3으로 이동

재귀를 통해 1) ~ 3)번 과정 반복

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/11729.cpp

#include <iostream>
#include <cmath>

using namespace std;

void solve(int n, int start, int end) {
    if (n == 0) return;
    solve(n - 1, start, 6 - start - end);
    cout << start << " " << end << "\n";
    solve(n - 1, 6 - start - end, end);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    cout << (int)pow(2, n) - 1 << "\n";
    solve(n, 1, 3);
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/11729.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        sb.append((int)Math.pow(2, n) - 1).append("\n");
        solve(n, 1, 3, sb);
        System.out.println(sb);
    }

    public static void solve(int n, int start, int end, StringBuilder sb) {
        if(n == 0) return;
        solve(n - 1, start, 6 - start - end, sb);
        sb.append(start).append(" ").append(end).append("\n");
        solve(n - 1, 6 - start - end, end, sb);
    }
}