[1463번] 1로 만들기 (Dynamic Programming)

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 다이나믹 프로그래밍(Dynamic Programming)

2. 1부터 답으로 가는 방식

DP를 이용하는 문제이다. 이 문제는 DP로 풀어낼 때, 답에서 1로 가도 되지만, 1에서 답으로 가는 방식을 이용하게 된다면,

만약 입력에 여러번 답을 호출하는 경우가 있었다면 훨씬 유리할 것이다.

즉, 입력이 10번이루어져 10 100 11 110 12 120 13 18 300 10000이라는 입력이 있었다면

1부터 10000까지 아에 DP를 통해 답을 모두 다 구해놓을 수 있기 때문이다.

이번 문제 DP의 점화식은 다음과 같다.

if ((i - 1) % 3 == 0)

a = DP[(i - 1)/3] + 2;

if (i % 6 == 0)

b = DP[i / 3] + 1;

if (i % 2 == 0)

c = DP[i / 2] + 1;

if (i % 3 == 0)

d = DP[i / 3] + 1;

e = min(DP[i - 1] + 1, DP[i - 2] + 2, DP[(i-1)/2] + 2, empty, empty);

a는 DP[(i-1)/3]을 했을 때 존재하는 값

b는 DP[i / 6]을 했을 때 존재하는 값

c는 DP[i / 2]을 했을 때 존재하는 값

d는 DP[i / 3]을 했을 때 존재하는 값

e는 DP[i-1]값과 DP[i-2]값과 DP[(i-1)/2]를 했을 때 존재하는 값 중 최솟값이다.

a~e까지 모두 구한 후, 최종적으로 이중 가장 작은 값을 구하면 된다.

DP[i] = min(a, b, c, d, e);

예를 들어 13이라는 수를 보자.

13에 대해 a는 DP[4]이다.

13에 대해 b는 존재하지 않는다.

13에 대해 c는 존재하지 않는다.

13에 대해 d는 존재하지 않는다.

13에 대해 e는 DP[12], DP[10], DP[6]이다.

그렇다면 DP[4], DP[6], DP[12], DP[10]에 대해 가장 최솟값을 찾으면 되는데

DP[4] = 2, DP[6] = 2, DP[10] = 3, DP[12] = 3이니 (미리 구한 값, 같은 방식으로 구하면 된다.)

DP[13]은 이중 가장 작은 값인 DP[4] + 2가 될것이다. (여기서 +2는 소스코드에서 확인할 수 있다.)

** 

DP는 처음에는 조금 까다롭고, 생각하기가 힘들 수 있지만, 

하나하나 생각하고 적어가다가 그에따른 규칙을 적용하면 되는 알고리즘이다.

처음에 고민하는 방법은 각자의 나름이지만, 필자는 항상 DP를 풀때 이런 방식으로 메모장에 dp[0]부터 dp[10]까지는

어떻게 구성되고 돌아가는지 한번 생각해보고 DP문제를 접근한다.

**

소스 코드 : 

#include <stdio.h>
 
int min(int a, int b, int c, int d, int e)
{
    if (a <= b && a <= c && a <= d && a <= e)
        return a;
 
    else if (b <= a && b <= c && b <= d && b <= e)
        return b;
 
    else if (c <= a && c <= b && c <= d && c <= e)
        return c;
 
    else if (d <= a && d <= b && d <= c && d <= e)
        return d;
 
    else
        return e;
}
 
int arr[1000002];
int DP[1000002] = { 0,0,1,1 };
 
int main()
{
    int n;
    int a, b, c, d, e, f;
    int empty = 100;
 
    scanf("%d", &n);
 
    for (int i = 4; i <= n; i++)
    {
        a = empty; b = empty; c = empty; d = empty; e = empty;
 
        if ((i - 1) % 3 == 0)        a = DP[(i - 1)/3] + 2;
 
        if (i % 6 == 0)        b = DP[i / 3] + 1;
 
        if (i % 2 == 0)        c = DP[i / 2] + 1;
 
        if (i % 3 == 0)        d = DP[i / 3] + 1;
 
        e = min(DP[i - 1] + 1, DP[i - 2] + 2, DP[(i-1)/2] + 2, empty, empty);
 
        DP[i] = min(a, b, c, d, e);
    }
 
    printf("%d", DP[n]);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>