[C++] 백준 1463번 - 1로 만들기

다이나믹 프로그래밍을 활용해서 푸는 문제이다

이게 조건 3개를 잘 선택해서 배열에 계속 더해야 한다

이 부분을 생각하는데 정말 많은 시간을 소비했다

 

#include <iostream>
using namespace std;

int dp[1000001];

int main() {

	int n;
	cin >> n;

	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];

	return 0;
}