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

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

1463번: 1로 만들기

 

풀이

DP

• N에서 1을 만드는 방법을 생각하지 않고, 1에서 N을 만드는 방법으로 구현한다. (bottom-up)
• N = 1인 경우 f[1]에 0을 넣고(basecase) 1에서 +1, *2, *3을 했을 때의 값인 f[2], f[3]에 1(f[1] + 1)을 넣는다.
• 즉, f[i+1] = f[i*2] = f[i*3] = f[i] + 1 이다.
• 다만 i보다 더 큰 수(j)로부터 최소의 횟수를 만들 수 있으므로 min(f[i] + 1(현재값), f[j] + 1)으로 값을 업데이트한다.
• 주의사항) 1에서 N이 되는 방식으로 구현했기 떄문에 N의 최대인 1000000에 맞춰 배열 f의 크기를 3000003으로 잡아야 한다. (좋은 방식은 아니겠지만..)

 

소스코드

#include <iostream>
using namespace std;

int f[3000003];

int dp(int x){
    for(int i=1; i<1000001; i++){
        if(!f[i+1])    f[i+1] = f[i] + 1;
        else f[i+1] = min(f[i+1], f[i] + 1);

        if(!f[i*2])    f[i*2] = f[i] + 1;
        else f[i*2] = min(f[i*2], f[i] + 1);

        if(!f[i*3]) f[i*3] = f[i] + 1;
        else f[i*3] = min(f[i*3], f[i] + 1);
    }
    return f[x];
}

int main(){
    int x;
    cin>>x;
    cout<<dp(x);
    return 0;
}