백준 1463_1로 만들기

1463번: 1로 만들기

 

동적계획법을 사용한 문제

 

Top_down 재귀문을 사용해 풀이하면...

n에 대해 min(3또는 2로 나눈 경우, n-1의 경우)에서 작은 값만을 선택해가면서 답을 구할 수 있다.

 

ex)

10

10은 2로 나누어지기 떄문에 min(make_1(5), make_1(9))

 

5는 1+make_1(4)

9는 1+min(make_1(3), make_1(8))

 

...

 

10 -> 9 -> 3 -> 1 

결과값 : 4

#include <stdio.h>
int min(int a, int b){
        return a > b ? b : a;   //최소값 return
}
int make_1(int n){
        if(n==1)
                return 0;
        if(!(n%3))
                return 1+min(make_1(n/3), make_1(n-1));
        if(!(n%2))
                return 1+min(make_1(n/2), make_1(n-1));
        return 1+make_1(n-1);
}
int main(){
        int n;
        scanf("%d",&n);
        printf("%d\n", make_1(n));
        return 0;
}