[백준] 1463 - 1로 만들기 (C++)

문제 출처 :

www.acmicpc.net/problem/1463

1463번: 1로 만들기

문제 풀이 :

• 입력값 n에 대해서 3으로 나눌수 있다면 3으로 나눠보고, 2로 나눌 수 있다면 2로 나눠보고 , 나머지 경우에 대해서 생각해보시는 식으로 점화식을 설계하였다.
• 재귀 함수를 통해 작성하였는데 통과는 하였다.
• 푸는 과정에서 느낀점은 DFS 처럼 이미 답이 나왔는데도 그 외의 경우도 모두 확인하는 경우가 나오는데 C++ 언어 특성상 속도에 강점이 있기 때문에 통과한거라고 생각한다(python으로 똑같은 로직으로 짠다면 시간초과가 난다)

#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 987654321;
int dp[1000001];

void init_()
{
    dp[1]=0;
    dp[2]=1;
    dp[3]=1;
    dp[4]=2;

    for(int i =5;i<1000001;i++)
    {
        dp[i]=INF;
    }
}

int solve(int n){

    if(dp[n]!=INF)
    {
        return dp[n];
    }

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

    return dp[n];
}

int main()
{
    int num = 0;
    cin >> num;
    init_();
    cout << solve(num)<<endl;
}