백준] 1463 - 1로 만들기

시간 제한 : 2초

메모리 제한 : 128MB

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최소값을 출력한다.

소스코드

#include <iostream>
#define MIN(a,b) ((a)<(b)?a:b)
using namespace std;
int DP(int n)
{
    int* table = new int[n + 1];
    table[1] = 0;
    
    for (int i = 2; i <= n; i++)
    {
        table[i] = table[i - 1] + 1;
        if (i % 2 == 0)
        {
            table[i] = MIN(table[i], table[i / 2]+1);
        }
        if(i%3==0)
        {
            table[i] = MIN(table[i], table[i / 3] + 1);
        }
    }
    return table[n];
}
int main(void)
{
    int n;
    cin >> n;
    cout << DP(n);
    return 0;
}

Tip

아주 1차원적인 동적 계획법으로 쉽게 풀 수 있따. 문제에서 3으로 나누어 떨어지는 경우, 2로 나누어 떨어지는 경우에 그렇지 않은 경우에는 1을 더하는 케이스를 조사하면서 연산 횟수에 따른 최솟값(최적해)를 구해나가면 된다.

table[i] = table[i - 1] + 1;

if (i % 2 == 0)

table[i] = MIN(table[i], table[i / 2]+1);

if(i%3==0)

table[i] = MIN(table[i], table[i / 3] + 1);