1463. 1로 만들기

1. 해결방법

• Dynamic Programming 문제이다.
• DP[n] 의 의미는 n을 1로 만들 수 있는 최소 연산 횟수이다.
• DP[0] = DP[1] = 0 ☞ 0은 범위 밖이고, 1을 1로 만들기 위한 연산은 0번이기 때문이다.
• DP[2] = 1, DP[3] = 1 
• 그렇다면 DP[4] 는 ??? DP[4] 는 N-1 로 3으로 만들고(1회) + DP[3] 이다.
• 즉, DP[N] = DP[N-1] + 1  또는  DP[N] = DP[N/2] + 1  또는  DP[N] = DP[N/3] + 1 이다.

 

2. Solution

// Dynamic Programming
#include <iostream>
#include <vector>

#define MAX 1000000 + 1
#define endl "\n"

using namespace std;

int N, answer = 0;
int DP[MAX];

void Input()
{
    cin >> N;
}

void Solution()
{
    DP[0] = 0;
    DP[1] = 0;

    for(int i = 2; i <= N; i++)
    {
        DP[i] = DP[i - 1] + 1;
        if(i % 3 == 0) DP[i] = min(DP[i], DP[i / 3] + 1);
        if(i % 2 == 0) DP[i] = min(DP[i], DP[i / 2] + 1);
    }

    cout << DP[N] << endl;
}

int main()
{
    Input();
    Solution();
    return 0;
}