[PS][DP]/[BOJ][1463][1로 만들기]

boj1463.cpp

#include <iostream>
#include <queue>

using namespace std;

int dp[1000001];

int main(void) {
	int n = 0;
	cin >> n;
	queue<int> q;
	q.push(1);
	dp[1] = 0;
	int curr = 0;
	while (!q.empty()) {
		curr = q.front();
		q.pop();
		if (curr * 3 <= n && !dp[curr * 3]) {
			dp[curr * 3] = dp[curr] + 1;
			q.push(curr * 3);
		}
		if (curr * 2 <= n && !dp[curr * 2]) {
			dp[curr * 2] = dp[curr] + 1;
			q.push(curr * 2);
		}
		if (curr + 1 <= n && !dp[curr + 1]) {
			dp[curr + 1] = dp[curr] + 1;
			q.push(curr + 1);
		}
	}
	cout << dp[n] << "\n";
	return 0;
}

//틀린 풀이
//10 입력하면 4가 출력된다.

#include <iostream>

using namespace std;

int dp[1000001];

int main(void) {
	int n = 0;
	cin >> n;
	dp[1] = 0;
	for (int i = 1; i <20; i++) {
		if (i * 3 <= n && !dp[i * 3]) dp[i * 3] = dp[i] + 1;
		if (i * 2 <= n && !dp[i * 2]) dp[i * 2] = dp[i] + 1;
		if (i + 1 <= n && !dp[i + 1]) dp[i + 1] = dp[i] + 1;
	}
	cout << dp[n];
	return 0;
}