문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

설명

DFS 접근 (시간초과)

  처음에는 시간복잡도를 생각하지 않고 DFS를 통해서 1을 만들었습니다. 완전탐색을 할경우 전체경우를 탐색하기 때문에 입력값이 크면 시간초과를 하게 됩니다.

DFS 코드

#include<stdio.h>
int min = 2147000000;
int DFS(int v, int d) {
    printf("%d\n",v);
    if(v == 1) {
        if(d < min) {
            min = d;
        }
    }else {
        if(v % 3 == 0) {
            DFS(v/3,d+1);
        }
        if( v % 2 == 0) {
            DFS(v/2,d+1);
        }
        DFS(v-1,d+1);
    }
}
int main() {
    int a;
    scanf("%d",&a);
    DFS(a,0);
    printf("%d",min);
    return 0;
}

Dynamic Programming(동적계획법)

dp[i]를 i 라는 숫자를 만들 수 있는 최소 계산 수 라고 가정 하겠습니다.
i라는 숫자를 1로 만들때, 1을 빼는방법, 2를 나누는방법, 3을 나누는방법이 있습니다. 따라서 아래와 같이 점화식을 찾아낼 수 있습니다.

dp[1] = '1을 만들 수 있는 최소 계산 수' = 0번
dp[2] = '2를 만들 수 있는 최소 계산 수' = 1번
dp[3] = '3을 만들 수 있는 최소 계산 수' = 1번
dp[4] = '4를 만들 수 있는 최소 계산수' = 2번
dp[5] = '5를 만들 수 있는 최소 계산수' = 3번
dp[6] = '6을 만들 수 있는 최소 계산수' = 2번

dp[6] = (1) dp[5] + 1, (2) dp[3] + 1, (3) dp[2] + 1 중 최소값이 됩니다.
dp[5] = (1) dp[4] + 1
dp[4] = (1) dp[3] + 1, (2) dp[2] + 1 중 최소값이 됩니다.

DP 코드

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