백준 1463번 문제. 1로 만들기

백준 1463번 문제. 1로 만들기

[Point] 다이나믹 프로그래밍으로 차근차근 부분해부터 구해나간다

자칫 막막해보일 수 있지만 다이나믹 프로그래밍의 관점에서 곰곰이 공략법만 제대로 짚어내면 쉬운 문제다.

*변수 설명*

N : 입력 변수

DP[x] : x라는 숫자를 1로 만들기 위해 필요한 "최소 연산의 횟수". 1의 경우엔 0번의 연산, 2와 3의 경우엔 1번의 연산이면 충분하고 최종해를 구하기 위한 최소한의 기본해이므로 미리 초기화해준다. 

temp : 각각의 연산으로 나온 DP[x]의 값을 미리 저장하는 변수. 이 변수를 DP[x]값과 비교하여 더 작은 값을 DP[x]에 넣어준다

*알고리즘 설명*

D[N] 은 다음 후보 중 가장 작은 값이 될 것이다.

1번 후보. D[N-1] + 1 

2번 후보. D[N/2] + 1 (단, N은 2로 나누어 떨어져야 함)

3번 후보. D[N/3] + 1 (단, N은 3으로 나누어 떨어져야 함)

이걸 위한 코드 작성만 해두면 끗 . 쉽다.   

#include <stdio.h>
#include <stdlib.h>
 
int main(){
 
    int N,i,temp;
    int* DP;
 
    scanf("%d",&N);
 
    DP=(int*)malloc(sizeof(int)*(N+1));
 
    DP[1]=0;
    DP[2]=1;
    DP[3]=1;
 
    for(i=4;i<=N;i++){
        DP[i]=DP[i-1]+1;
 
        if(i%2==0){
            temp=DP[i/2]+1;
            if(temp<DP[i]){
                DP[i]=temp;
            }
        }
        if(i%3==0){
            temp=DP[i/3]+1;
            if(temp<DP[i]){
                DP[i]=temp;
            }
        }
    }
 
    printf("%d\n",DP[N]);
 
    free(DP);
    return 0;
}