[백준 c++] 1463 1로 만들기

문제

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

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

위의 연산 3개를 적절히 사용해서 1을 만들려고 할 때 연산을 사용하는 횟수의 최솟값을 구하는 문제다.

풀이

이 문제는 곧이 곧대로 풀면 시간초과 또는 틀린 답이 나온다.
처음에는 재귀를 이용해서 가능한 모든 연산의 경우의 수를 구했는데 시간초과가 나버렸다..

이 문제는 1부터 N까지 1로 만들기까지의 최소 연산의 수를 배열에 저장해서 풀 수 있었다.

이 때 중요한 것은 어떤 연산을 어떤 순서로 해야 최소 연산인지는 모른다는 것이다. 빼기보다 나누기 연산을 해야 무조건 연산의 수가 더 작은 것은 아니다.
만약 N = 10 이라면 dp[9]+1과 dp[5]+1을 비교해서 더 작은 값을 택해야할 것이다. 이때 dp[9] = 2, dp[5] = 3로 dp[9]+1을 택하는게 답이다.

따라서 모든 3가지 경우를 모두 고려하고 그 중 최솟값을 저장해줘야 한다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, dp[1000001];
int main()
{
    cin >> n;
    dp[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        if (i % 2 == 0 && i % 3 == 0)
        {
            dp[i] = min(dp[i / 3] + 1, dp[i - 1] + 1);
            dp[i] = min(dp[i / 2] + 1, dp[i]);
        }
        else if (i % 3 == 0)
            dp[i] = min(dp[i - 1] + 1, dp[i / 3] + 1);
        else if (i % 2 == 0)
            dp[i] = min(dp[i - 1] + 1, dp[i / 2] + 1);
        else
            dp[i] = dp[i - 1] + 1;
    }
    cout << dp[n] << "\n";
    return 0;
}