백준 1463번: 1로 만들기(작성중)

- DP를 사용해서 풀었습니다.

- top-down(recursive)가 아닌 bottom-up(loop) 방식을 사용했습니다.

 

아래 점화식 중에서 최소값을 찾으면됩니다.

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

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

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

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;

    cin >> n;

    int dp[1000001] = {};

    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;

    for (int i = 4; i <= n; i++)
    {
        int m = 100000000;

        if (i % 3 == 0)
        {
            m = dp[i / 3];
        }

        if (i % 2 == 0)
        {
            m = min(m, dp[i / 2]);
        }

        m = min(m, dp[i - 1]);

        dp[i] = m + 1;

    }

    cout << dp[n] << endl;
    return 0;
}

참고

https://blockdmask.tistory.com/254