백준 1463 1로 만들기

1) DP 점화식 정의
DP[x]를 x가 1이 되기 위한 최소 연산 횟수로 정의합니다.
따라서 DP[1]은 0이 되고 (초기값), dp[x]는 dp[x - 1] + 1; 입니다. (기본)
하지만, x가 2로 나누어 떨어지면, dp[x - 1] + 1, dp[x / 2] + 1중 최솟값을,
x가 3으로 나누어 떨어지면, dp[x - 1] + 1, dp[x / 3] + 1중 최솟값을 고릅니다.
그리고 dp[n]을 출력합니다.

2) source code

#define ll long long
#define pii pair<int, int>
#define mod 10000007
#define INF 100000000
#define pb push_back
#define pi 3.141592
using namespace std;

int dp[1010101];


int main(void){

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    int n;
    cin >> n;

    dp[1] = 0;

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

    cout << dp[n];


    return 0;
}