1로 만들기

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

1463번: 1로 만들기

다이나믹 프로그래밍의 기본 문제

Bottom-up

D[i]를 만들어 가는 것

#include <iostream>
#include <vector>
using namespace std;
int d[1000001];
 
int main()
{    
    int n;
    cin >> n;
 
    d[1] = 0;
 
    for (int i = 2; i <= n; i++)
    {
        d[i] = d[i - 1] + 1;
        if ((i % 2 == 0) && d[i] > d[i / 2] + 1)
            d[i] = d[i / 2] + 1;
 
        if ((i % 3 == 0) && d[i] > d[i / 3] + 1)
            d[i] = d[i / 3] + 1;
    }
 
    cout << d[n] <<'\n';
    
    return 0;
}

Top-down

#include <iostream>
using namespace std;
int d[1000001];
 
int go(int n)
{
    if (n == 1)
        return 0;
    if (d[n] > 0)
        return d[n];
 
    d[n] = go(n - 1) + 1;
 
    if (n % 2 == 0)
    {
        int temp = go(n / 2) + 1;
        if (d[n] > temp)
            d[n] = temp;
    }
 
    if (n % 3 == 0)
    {
        int temp = go(n / 3) + 1;
        if (d[n] > temp)
            d[n] = temp;
    }
    return d[n];
}
 
 
int main()
{    
    int n;
    cin >> n;
    cout << go(n) <<'\n';
    return 0;
}