1로 만들기 (DP)

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>

#define N 1000000

int dp[N];

void fibo(int n)

{

for (int i = 2; i <= n; i++)

{

dp[i] = dp[i - 1] + 1;                                    

if (i % 2 == 0)

{

if (dp[i] > dp[i / 2] + 1)

dp[i] = dp[i / 2] + 1;

}

if (i % 3 == 0)

{

if (dp[i] > dp[i / 3] + 1)

dp[i] = dp[i / 3] + 1;

}

}

}

int main()

{

    int a;

    scanf("%d",&a);

fibo(a);

    printf("%d",dp[a]);

}

DP 에서 bottom - up 으로 풀었다.

DP는 배열에다 메모이제이션하는 방법으로 동일한 방법의 계산을 반복할때, 이전의 값들을 저장하는 방법인데

이 문제를 보면 

입력이 주어졌을때 위의 세가지 규칙들을 이용하여  입력된 수를 1로 최소한의 횟수로 만드는 문제

1에서 1로 만들때 드는 횟수는 당연히 0번   ---> 배열1에는 0삽입

1에서 2로 만들때 드는 방법은 2가지가 있다. 1에서 +1 하는 경우 or 1에서 x2하는 경우  하지만 둘다 횟수 1번으로 동일하기 때문에 --> 배열2에는 1삽입 

1에서 3으로 만들때 드는 방법은 2가지 -->  1에서 x3 하는 경우  or  2에서 +1 하는 경우 ,     이때 1에서 x3 하는 경우는 횟수가 1번이지만 ,  2에서 +1 하는 경우는 횟수가 2번이다.  왜냐하면  1에서 2로 갈때 벌써 횟수1번을 소모했으니 2에서 3으로갈때 총 횟수가 2번이다   

그래서  3으로 만들때 드는 가장 최소한의 횟수는 1번이다.(1에서 x3한 방법)

만약 입력이 11이라면 배열은 요로코롬 만들어질것.