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

 

 

 

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

 

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

---

 

해결전략

 

동적계획법 (Dynamic Programming) DP

 

dp[1] = 0

---

 

코드

 

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

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> dp(n+1);

	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;

	for (int i = 4; 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];

	return 0;
}