[DP] https://www.acmicpc.net/problem/1463

01. 문제

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

1463번: 1로 만들기

02. 코드

//1로만들기 
//알고리즘 분류: DP
#include <iostream>
#include <algorithm>
using namespace std;
int dp[1000001];

int main()
{
	int n;

	//input
	cin >> n;

	//sol 
	dp[1] = 0;
	for (int i = 2; i <= n; i++) { //2345678910
		dp[i] = dp[i - 1] + 1; 
		//cout << "(i, dp[i]): " << i << "," << dp[i] << endl;

		if (i % 3 == 0) {
			dp[i] = min(dp[i], dp[i / 3] + 1); 
			//cout << "(i, dp[i]): " << i << "," << dp[i] << endl;
		}
		else if (i % 2 == 0) {
			dp[i] = min(dp[i], dp[i / 2] + 1);
			//cout << "(i, dp[i]): " << i << "," << dp[i] << endl;
		}
	}

	//output
	cout << dp[n];

}

03. 풀이 

1까지 나온 경우의 수 중 최소 값을 dp[1]에 저장

2까지 나온 경우의 수 중 최소 값을 dp[2]에 저장

3까지 나온 경우의 수 중 최소 값을 dp[3]에 저장

4까지 나온 경우의 수 중 최소 값을 dp[4]에 저장

....

n까지 나온 경우의 수 중 최소 값을 dp[n]에 저장