[BOJ] 1463번: 1로 만들기

1463번: 1로 만들기

풀이

스타트링크의 최백준님께서 유튜브에 올리신 DP 강좌를 발견했습니다. 필요하신 분은 보시기 바랍니다. 
링크

1. 동적 프로그래밍으로 풀 수 있다.
2. X를 2로 나눌 때, 3으로 나눌 때, 1를 뺄 때의 최소값을 이전 값들을 이용해 계속 업데이트를 해주면 된다

다음 그림과 같이 N = 10일 때 1이 되기 까지의 대략적인 그림을 나타낸 것이다. 문제 해결 방식으로는 2가지가 있다.

1. 10에서 9와 5의 가지를 내릴 수 있는데 사실 이 두 개로는 결과를 도출해 낼 수 없다. 그래서 어쩔 수 없이 각각에 또 다른 뿌리를 내려서 1까지 내려가 얼마나 연산을 해야 하는지 계산할 수 밖에 없다. 이것은 재귀함수로 구현할 수 있는 방식이다.(Top-down)
   
   
2. 또 다른 방식으로는 아래서 위로 올라가는 방식이다. 위에서 내려갈 때는 수 많은 경우가 있어서 컴퓨터의 연산 속도를 이용할 수 있지만 좀 보기 별로인 것은 사실이다. 그래서 1과는 반대로 1부터 시작해서 N(=10)까지 올라가는 거다. 이것을 Bottom-up 방식이라고 한다.
    조금 다른 것은 [1, N]까지 진행하면서 계속 이전 값들을 이용한다. 이전 값들은 분명히 최적의 해가 들어있을 것이고 그것을 이용하기만 하면 된다.

방식은 이런데 문제 풀이 자체를 정리하자면 F(N) = N이 1이 되는 최소 연산 횟수라 했을 때,

 

F(N)은 { N % 3 == 0이라면 F(N/3)의 값, N % 2 == 0이라면 F(N/2), F(N - 1)의 값 } 중 최솟값 + 1이다.

코드(제 코드는 참고만 하시는 게...)

BOTTOM-UP 방식

#include <cstdio>
#include <algorithm>
using namespace std;
int N, dp[1000001];

int main()
{
    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;
}

TOP-DOWN 방식

#include <stdio.h>
int n;
int DP[1000001];

int func(int n)
{
    if (n == 1)
        return 0;
    if (DP[n] > 0)
        return DP[n];
    DP[n] = func(n - 1) + 1;

    if (n % 2 == 0)
    {
        int tmp = func(n / 2) + 1;
        if (DP[n] > tmp)
            DP[n] = tmp;
    }
    if (n % 3 == 0)
    {
        int tmp = func(n / 3) + 1;
        if (DP[n] > tmp)
            DP[n] = tmp;
    }

    return DP[n];
}

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

    printf("%d\n", DP[n]);
    return 0;
}