[BOJ-1463]1로만들기

9달전에 풀었던 문제였는데 다시 한번 풀어보았다. 

이 문제를 요약하면, 입력으로 주어지는 수를 총 3가지 연산을 이용하여 1까지 만드는 최소 연산의 횟수를 구한다.

총 3가지 연산은 

1) 3으로 나눠지면 3으로 나눈다.

2) 2로 나눠지면 2로 나눈다.

3) -1 한다. 

입력의 범위는 [1, 1E+6] 

출력의 범위 또한 0부터 최대 1E+6보다는 작은 수 일 것이다.

그러면 이것을 만들기 위해서 값을 정해두고, 값을 계속 업데이트 하는 방식으로 코드를 작성했다.

dp[x] : 입력한 수부터 x까지 도달하는 최소 연산 횟수

void dy(int x) : 입력한 x 수에서 부터 다음 최소 연산 횟수를 구하기 위한 함수, 총 3가지연산을 시행했을 시 가능한 것을 업데이트 한다.

총 배열의 크기는 1E+6 개 보다 더 많게 설정하고, 모두 INF 으로 설정한다. 

그리고 매 시행마다 도달할 수 있는 최소 횟수를 업데이트 할 수 있다면, 업데이트 한다. 

9달전에 작성했을 때는 bottom-up 방식으로 작성했던 것 같다.

지금 작성한 방식은 top-down 방식으로 작성한 것이다.

#include<cstdio>
 
int res[1000002]={0,0,1,1};
int main(){
    int idx = 0 ;
    int tmp = 0;
    int minidx;
    int i ;
    int input;
    
    scanf("%d",&input);
    
    for(i = 4; i <= 1000000 ; i++){
        minidx = 1000000;
        
        if( i % 3 == 0 ) {
            minidx = res[i/3];
        }
        if( i % 2 == 0 ){
            if(minidx == 1000000){
                minidx = res[i/2];
            }else if(minidx > res[i/2]){
                minidx = res[i/2];
            }
        }
        if( minidx > res[i-1]){
            minidx = res[i-1];
        }
        
        res[i] = minidx + 1;
        
        if(i == input){
            break;
        }
    }
    printf("%d\n", res[input]);
    
    
    return 0;
}
 

#include<cstdio>
/*
input : [1,1E+6]
output : [0,1E+6]
cond-1 : X%3 == 0 -> X%3
cond-2 : X%2 == 0 -> X%2
cond-3 : X--
*/
const int INF = 1111111;
int dp[1111111];
void init_dp(){
    for(int i = 0 ; i < INF ; i++) dp[i] = INF;
}
int min_2(int a, int b){
    return (a>b)?b:a;
}
void dy(int x){
    if(x==0) return;
    if(x%3 == 0){
        if(dp[x/3] > dp[x]+1) dp[x/3] = dp[x]+1;
    }
    if(x%2 == 0){
        if(dp[x/2] > dp[x]+1) dp[x/2] = dp[x]+1;
    }
    if(dp[x-1] > dp[x]+1) dp[x-1] = dp[x]+1;
}
 
int main(){
    int X; scanf("%d", &X);    
    
    // operation
    init_dp();
    dp[X] = 0;
    for(int i = X ; i > 0 ; i--){
        dy(i);
    }
    // end operation 
 
    printf("%d\n",dp[1]);
    return 0;
}