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

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

 

세가지 연산을 적절히 사용해서 최소 연산 수를 통해 1로 만드는 연산을 해야하는데 이때 점화식을 만들어서 해보자.

우선 1을 뺐을때와 2로 나눴을때 3으로 나눴을때의 연산 수 비교해서 최소값 배열을 2부터n까지 계산해두고 필요한 수를 꺼내서 사용하면 된다.

 

 

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<int>dp(n + 1);

	dp[1] = 0;

	for (int i = 2; i <= n; i++)
	{
		//우선 1빼보기
		dp[i] = dp[i - 1] + 1;
		if (i % 2 == 0)
		{
			//1뺐을때와 2로 나누었을때 비교
			dp[i] = min(dp[i], dp[i / 2] + 1);
		}
		if (i % 3 == 0)
		{
			//1뺐을때와 3로 나누었을때 비교
			dp[i] = min(dp[i], dp[i / 3] + 1);
		}
	}

	cout << dp[n];
}