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

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

문제 해석

• 동적계획법을 이용하여 1로 만드는 연산의 최소값을 구한다

알고리즘 분류

• 동적계획법(dp)

풀이

• dp[1], dp[2], dp[3]을 미리 초기화한다
• 점화식을 세워 n까지 연산한다

코드

#include <iostream>
#include <string>
#include <vector>
#include <cmath> 
#include <algorithm>
using namespace std;

int dp[1000001];

int main() { 
    long n;
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;

    cin >> n;

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