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

문제

 

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

---

 

풀이

 

/3 , /2를 한 수에서 1을 더한 값과, -1를 한 수에서 1을 더한 값 중에

더 작은 값을 dp 배열에 대입한다

 

---

 

코드

 

#include <stdio.h>
#include <stdlib.h>

int N;
int dp[1000001]; //i의 범위만큼 -> DP함수에서 dp[i+1]로 선언해도 좋음

int min3(int a, int b, int c)
{
    if(a<=b && a<=c)
        return a;
    else if(b<=a && b<=c)
        return b;
    else if(c<=a && c<=b)
        return c;
}

int min2(int a, int b)
{
    if(a <= b)
        return a;
    else
        return b;
}

void dfs(int n) //Top-Down 방식으로, 재귀함수를 이용한다
{
    if(dp[n] == 0) //필수 조건
    {
        if(n == 1)
            dp[1] = 0;
        else if(n == 2)
            dp[2] = 1;
        else if(n == 3)
            dp[3] = 1;
        else
        {
            if(n%3 == 0 && n%2 == 0)
            {
                dfs(n/3);
                dfs(n/2);
                dfs(n-1);
                dp[n] = min3(dp[n/3], dp[n/2], dp[n-1]) + 1;
            }
            else if(n%3 == 0)
            {
                dfs(n/3);
                dfs(n-1);
                dp[n] = min2(dp[n/3], dp[n-1]) + 1;
            }
            else if(n%2 == 0)
            {
                dfs(n/2);
                dfs(n-1);
                dp[n] = min2(dp[n/2], dp[n-1]) + 1;
            }
            else
            {
                dfs(n-1);
                dp[n] = dp[n-1] + 1;
            }
        }
    }
}

int main()
{
    scanf("%d", &N);

    dfs(N);

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

    return 0;
}