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

문제는 여기!

문제 해결 방법

DP[n] : n을 만드는데 사용되는 연산의 최소 횟수 로 정하고

Dp{1] = 0,DP[2] = 1, DP[3] = 1, 나머지는 N으로 초기화를 했다.

그리고 n이 3으로 나누어 떨어지면 DP[n]과 DP[n/3]+1 의 최소값을 비교해서 DP[n]에 입력,

n이 2로 나누어 떨어지면 DP[n]과 DP[n/2]+1 의 최소값을 비교해서 DP[n]에 입력,

DP[n]과 DP[n-1]+1 의 최소값을 비교해서 DP[n]에 입력해서 문제를 해결했다.

#include <bits/stdc++.h>

using namespace std;

int N;
int dp[1000001];

void solve(){
    for(int i=4; i<=N; i++){
        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);
        dp[i] = min(dp[i],dp[i-1]+1);
    }
}

void input(){
    cin >> N;
    fill(dp, dp+N+1, N);
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    if(N>=4) solve();

    cout << dp[N];

    return 0;
}