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

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

풀이

점화식을 사용하는 문제는 아니지만, 매번 새로 계산을 하는 것이 아니라 이미 계산된 값은 배열에 저장해서 시간을 줄여야 하는 문제였다.

먼저 배열에 n의 범위보다 큰 값을 저장해두고,
2부터 n까지 모든 단계에서, 세 가지 연산 중 1로 만들기에 가장 적은 횟수를 필요로 하는 것을 선택한다.

코드 : bottom-up

#include <iostream>
using namespace std;

const int MAX = 1e7;
int dp[1000001];

int main()
{
    int n;
    cin >> n;
    
    dp[1] = 0;
    for(int i=2; i<=n; i++){
        dp[i] = MAX;
    }
    
    for(int i=2; i<=n; i++){
        dp[i] = dp[i-1] + 1;
        if(i % 3 == 0) dp[i] = min(dp[i], dp[i/3] + 1);
        if(i % 2 == 0) dp[i] = min(dp[i], dp[i/2] + 1);
    }
    cout << dp[n];

    return 0;
}

코드 : top-down

#include <bits/stdc++.h>
using namespace std;

int opnum[1000001];

int dp(int n) {
    if(n == 1) return 0;
    if(opnum[n]) return opnum[n];

    int res = dp(n - 1) + 1;

    if(n % 3 == 0) res = min(dp(n / 3) + 1, res);
    if(n % 2 == 0) res = min(dp(n / 2) + 1, res);
    return opnum[n] = res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    cout << dp(N);

    return 0;
}