[C++] 백준 1463번

1로 만들기 𝟙

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다

〰️

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

1463.cpp

#include <iostream>

int main(int argc, const char * argv[]) {
    
    int N;
    std::cin >> N;
    
    int dp[1000001] = {0,};
    
    dp[1] = 0;
    
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i-1] + 1;
        if (i % 3 == 0)
            dp[i] = std::min(dp[i], dp[i/3] + 1);
        if (i % 2 == 0)
            dp[i] = std::min(dp[i], dp[i/2] + 1);
    }
    
    std::cout << dp[N];
    
    return 0;
}

익숙한 문제인데 기억이 잘 안나긴 했다^^...