문제 소개 📌

문제 링크 📢

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

문제 풀이 📝

문제에서는 3가지 연산을 사용하여 주어진 정수 N을 1로 만드는 연산의 횟수의 최솟값을 구해야 한다. 하지만 각각의 수 별로 최솟값이 되는 방식은 갖가지이므로 우리는 N 전까지의 모든 수들의 1로 만드는 연산의 최솟값을 dp배열에 연산 횟수를 갱신하면서 올라가 N의 최소 연산 횟수를 구해야 한다. 시간복잡도는 N이고, N은 1,000,000까지므로 시간제한인 0.15초안에 충분히 들어온다.
조건문의 순서는 현재 갱신하려는 수가 2와 3의 공배수인지, 3의 배수인지, 2의 배수인지, 모두 아닌지 순서로 확인한다.
이 때 모든 조건엔 3번 연산인 '1을 뺀다'가 추가되어야 모든 경우의 수를 따질 수 있다!!

코드

#include<iostream>
#include<algorithm>

using namespace std;

int dp[1000000];
int make_number1(int n)
{
	if (dp[n] == 0 && n > 1)
	{
		if (n <= 3)
		{
			dp[n] = 1;
			return dp[n];
		}
		
       //2와 3의 공배수인지?
		if (n % 3 == 0 && n % 2 == 0)
			dp[n] = min(min(make_number1(n - 1), make_number1(n / 2)), make_number1(n / 3)) + 1;
		else if (n % 3 == 0) //3의 배수인지?
			dp[n] = min(make_number1(n - 1), make_number1(n / 3)) + 1;
		else if (n % 2 == 0) // 2의 배수인지?
			dp[n] = min(make_number1(n - 1), make_number1(n / 2)) + 1;
		else // 모두 아니라면 1을 뺀다.
			dp[n] = make_number1(n - 1) + 1;
	}
	return dp[n];
}
int main()
{
	int N;
	cin >> N;
	cout << make_number1(N);
	return 0;
}