[백준 1463번] 1로 만들기 C++

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

동적계획법을 공부하기 위해서 풀게된 문제.

탑다운과 바텀업 방식으로 정말 해답을 보고 따라풀며 이해하려고 노력했습니다.

DP는 좀 어려운듯 ㅜㅜ

 

 

 

 

탑다운

#include <cstring>
#include <iostream>
#include <algorithm>
 
using namespace std;
int dp[1000001];
 
 
int f(int n) {
    if (n == 1) return 0;
    //메모이제이션
    if (dp[n] != -1) return dp[n];
 
    int result = f(n - 1) + 1;
    if (n % 3 == 0) result = min(f(n / 3) + 1, result);
    if (n % 2 == 0) result = min(f(n / 2) + 1, result);
 
    dp[n] = result;
    return result;
}
 
int main() {
    int n;
    cin >> n;
    memset(dp, -1, sizeof(dp));
    cout << f(n);
    return 0;
}

 

 

 

바텀업

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int n, dp[1000001];
    cin >> n;
 
    fill(dp, dp + 1000001, 1000000000);
    dp[1] = 0;
    for (int i = 1; i < n; i++) {
        dp[i + 1] = min(dp[i + 1], dp[i] + 1);
        if (i * 3 <= n) dp[i * 3] = min(dp[i * 3], dp[i] + 1);
        if (i * 2 <= n) dp[i * 2] = min(dp[i * 2], dp[i] + 1);
 
    }
 
    cout << dp[n];
    return 0;
}