[BOJ] 1463. 1로 만들기

문제

www.acmicpc.net/problem/1463

1463번: 1로 만들기

---

코드

#include<iostream>
#include<algorithm>
using namespace std;

int DP[1000001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	DP[1] = 0;
	int N;
	cin >> N;

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