백준 1463: 1로 만들기(DP)

특별하게 어렵거나 쉽다기보단... DP 쥐뿔도 모르는 내가 꾸역꾸역 풀어본 문제라서 올려봄

#include <iostream>
 
int dp[1000010];
 
int main()
{
    int input, N;
    int cnt = 0;
    std::cin >> input;
    dp[2] = dp[3] = 1;
    N = 4;
    while (N <= input)
    {
        if (N % 3 == 0)
        {
            if (dp[N - 1] >= dp[N / 3])
                dp[N] = dp[N / 3] + 1;
        }
        if (N % 2 == 0)
        {
            if (dp[N - 1] >= dp[N / 2])
            {
                if (dp[N] == 0)
                    dp[N] = dp[N / 2] + 1;
                else if(N % 3 == 0)
                    if(dp[N] > dp[N / 2])
                        dp[N] = dp[N / 2] + 1;
            }
        }
        if(dp[N] >= dp[N - 1] + 1 || dp[N] == 0)
            dp[N] = dp[N - 1] + 1;
        ++N;
    }
    int i = dp[input];
    std::cout << i;
    return 0;
}

이건 겨우겨우 풀어댄 방법

#include <iostream>
 
int dp[1000010];
 
int main()
{
    int input, N;
    int cnt = 0;
    std::cin >> input;
    dp[2] = dp[3] = 1;
    for (int N = 4; N <= input; ++N)
    {
        dp[N] = dp[N - 1] + 1;
        if (N % 3 == 0)
            dp[N] = dp[N] > dp[N / 3] + 1 ? dp[N / 3] + 1 : dp[N];
        if (N % 2 == 0)
            dp[N] = dp[N] > dp[N / 2] + 1 ? dp[N / 2] + 1 : dp[N];
    }
    std::cout << dp[input];
 
    return 0;
}

이건 훨씬 깔끔한 방법

DP의 핵심은, 반복문을 한큐에 끝낼 수 있는가

인듯.

브루트포스처럼 코드가 이리흐르고 저리흐르면 망한다는 것이다

그러기 위해선 이곳저곳으로 흘러흘러가는 코드보다는

처음부터 끝까지 우직하게 지나가는(저장하는) 방식이 동적배열에 더 맞지 않는가 싶다.