[백준][1463번][DP] 1로 만들기

1로 만들기

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

<코드>

#include <stdio.h>
 
int Dp[1000001];
 
int min(int a, int b){
    return a > b ? b : a;
}
 
int main(void){
 
    int N;
    scanf("%d", &N);
 
    Dp[1] = 0;
 
    for (int i = 2; i <= N; i++)
    {
        Dp[i] = Dp[i - 1] + 1;
        if (i % 2 == 0)
            Dp[i] = min(Dp[i], Dp[i / 2] + 1);
        if (i % 3 == 0)
            Dp[i] = min(Dp[i], Dp[i / 3] + 1);
    }
 
    printf("%d\n", Dp[N]);
    return 0;
}

<문제 푼 요령>

1. Dp 테이블에 최소값을 꾸준히 집어넣는다고 가정을 한다면

2. Dp[i]값에 최소값이 들어갈 경우는 Dp[i-1] +1, Dp[i/2] +1, Dp[i/3] +1 값을 비교해서 최소값을 넣어 주면 된다. 

3. 쭉 진행해서 Dp[N]에 우리가 구하고자 하는 최소값이 들어오게 된다.