[C++][백준 1463][다이나믹 프로그래밍] 1로 만들기 :: seoftware

 문제 

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

1463번: 1로 만들기

 소스 

#include <iostream>
#include <algorithm>

using namespace std;
int dp[1000001] = { 0 };

int main(void) {
	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];
	return 0;
}

dp 코드를 짤 때마다 느끼는건데 dp 구할 때 가장 중요한 것은 배열과 관계식인 것 같다!