[백준 6092번] [동적 계획법] Strange Towers of Hanoi

Approach

사실 문제에서 접근 방법을 다 제시해서 쉽게 풀 수 있다.

하노이의 탑 알고리즘의 경우 recursion만 잘 활용해주면 쉽게 풀 수 있다.

 

hanoi[n] : 2 * hanoi[n - 1]  + 1 for i $\ge$ 2 (Define that hanoi[1] is 1)

dp[n] : min{hanoi[j] + 2 * dp[n - j]} for $ 1 \le j \le n$ (Define that dp[1] is 1)

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_With_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int hanoi[13];
int dp[13];

int hanoi_cal(int n){
    if(n == 1) return 1;
    return hanoi[n] =  2 * hanoi_cal(n - 1) + 1;
}

int main(void){
    hanoi[0] = 0;
    hanoi[1] = 1;
    hanoi_cal(12);
    dp[0] = 0;
    dp[1] = 1;
    
    cout << dp[1] << "\n";

    for(int i = 2; i <= 12; i++){
        int min_value = 987654321;
        for(int j = 1; j <= i; j++){
            if(min_value > hanoi[j] + 2 * dp[i - j]){
                min_value = hanoi[j] + 2 * dp[i - j];
            }
        }
        dp[i] = min_value;
        cout << min_value << "\n";
    }
    return 0;
}