백준 소스코드 [C++] 1463 1로 만들기 1-DP

www.acmicpc.net/problem/1463

1463번: 1로 만들기

백준 소스코드 [C++] 1463 1로 만들기 DP

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int DP[1000001];
int dp(int n) {
	DP[1] = 0;
	for (int i = 2; i <= n; i++) {
		DP[i] = DP[i - 1] + 1;
		if (i % 2 == 0 && DP[i] > DP[i / 2] + 1)
			DP[i] = DP[i / 2] + 1;
		if (i % 3 == 0 && DP[i] > DP[i / 3] + 1)
			DP[i] = DP[i / 3] + 1;
	}
	return DP[n];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	cout << dp(n);
	return 0;
}