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

다이나믹 프로그래밍 문제이다. 

실버 문제라서 그런지 식이 바로 떠올라서 바로 풀었다.

가장 i =1 부터 i+1 , i *2 , i*3 을 하나씩 계산해 주면 된다.

 

사실 3번 틀렸는데 이유가 dp[1] = 1이 아니라 dp[1] =0 이다.

dp[1] =1이라고 하면 100% 까지 가서 틀렸습니다가 뜬다.  

#include <bits/stdc++.h> 
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 987654321
typedef long long ll;
using namespace std;
int num;
int cnt=0;
int dp[1000005];
int main() {
	cin >> num;
	for (int i = 1; i <= num; i++) {
		dp[i] = INF;
	}
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	
	for (int i = 1; i <= num; i++) {
		if (i + 1 <= num)
			dp[i + 1] = min(dp[i]+1, dp[i + 1]);
		if (i * 2 <= num)
			dp[i * 2] = min(dp[i] + 1, dp[i * 2]);
		if(i*3 <= num)
			dp[i * 3] = min(dp[i] + 1, dp[i * 3]);
	}

	cout << dp[num];
}

dp 문제는 코딩은 참 쉬운데 구상이 어려운것 같다

근데 이문제는 구상도 쉬웠다 

덕분에 오늘 아주 쉽게 경험치 획득~