백준 1463(1로 만들기)

이제 본격적으로 dp 를 공부하면서 만난 첫번째 문제이다. 

top-down 방식으로 풀기를 원했지만 재귀가 아직 익숙하지 않아 bottom-up 으로 풀었다.

핵심로직은 2가지 이다.

1. 이전의 값을 이용해서 풀어야 한다.

2. 최초로 들어가 있던 값이 최소가 아닐 수 있다. 

#include <iostream>
#include <algorithm>

using namespace std;

int dp[3000001];
int X;

void dpFunc(int X) {
	for (int i = 1; i <= X; i++)
	{
		if (dp[i * 3] > dp[i] + 1) {
			dp[i * 3] = dp[i] + 1;
		}
		if (dp[i * 2] > dp[i] + 1) {
			dp[i * 2] = dp[i] + 1;
		}
		if (dp[i + 1] > dp[i] + 1) {
			dp[i + 1] = dp[i] + 1;
		}
	}
}

int main() {
	cin >> X;
	for (int i = 1; i <= X; i++)
	{
		dp[i] = 9000000;
	}
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;

	dpFunc(X);

	cout << dp[X];

	return 0;
}