[백준][DP] 1로 만들기

 

1463번: 1로 만들기

정수 N을 문제에서 주어진 3가지 연산을 가지고 1을 만들 때, 연산을 사용하는 횟수의 최솟값을 출력해야하는 문제이다.

 

다이나믹 프로그래밍 문제로 크기가 반복문을 이용하여 작은 문제부터 차례대로 풀어 나가는 Bottom-up 방식과 재귀함수를 이용하여 큰 문제를 작은 문제로 나누어서 푸는 방식인 Top-down방식으로 풀 수 있다.

 

1. Bottom-up

#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[100001];
int main(void)
{
    int n;
    cin >> n;
    arr[1] = 0; //1일 때 연산이 필요 없으므로 0을 입력한다.
    for (int i = 2; i <= n; i++)
    {
        arr[i] = arr[i - 1] + 1; //-1연산을 이용했을 때의 횟수를 입력한다. 가장 많은 연산을 하므로 비교대상이 된다.
        if (i % 2 == 0)
        {
            arr[i] = min(arr[i],arr[i/2]+1); //arr[i]에 입력되어 있는 수와 /2연산을 했을때 횟수를 비교하여 더 작은 수를 입력한다.
        }
        if (i % 3 == 0)
        {
            arr[i] = min(arr[i],arr[i / 3] + 1); //arr[i]에 입력되어 있는 수와 /3연산을 했을때 횟수를 비교하여 더 작은 수를 입력한다.
        }
    }
 
    cout << arr[n] << '\n';
    return 0;
}

2. Top-down

#include <iostream>
#include <algorithm>
using namespace std;
 
int td[1000001];
int topdown(int n)
{
    if (n == 1)
        return 0;
    if (td[n] > 0) 
        return td[n];
    td[n] = topdown(n - 1) + 1;
    if (n % 2 == 0)
    {
        td[n] = min(td[n], topdown(n / 2) + 1);
    }
    if (n % 3 == 0)
    {
        td[n] = min(td[n], topdown(n / 3) + 1);
    }
    return td[n];
}
 
int main(void)
{
    int n;
    cin >> n;
    cout << topdown(n) << '\n';
    return 0;
}