[BOJ 1463] 1로 만들기

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

1. dp를 이용해 계산한다.

#include <iostream>

#include <algorithm>

using namespace std;

#define MAX_N 1000001

int i, N, result;

int dp[MAX_N];

void input()

{

cin >> N;

}

void cal()

{

dp[1] = 0; dp[2] = 1; dp[3] = 1;

for (i = 4;i <= N;i++)

{

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

if ((i%3)==0) dp[i] = min(dp[i / 3] + 1, dp[i]);

if ((i%2)==0) dp[i] = min(dp[i / 2] + 1, dp[i]);

}

result = dp[N];

}

int main()

{

input(); cal();

cout << result;

}