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

 

풀이과정

---

재귀 함수를 사용해서 N%3==0, N%2==0 외에도 N-1 %3 ==0 , N-1 %2 ==0 , N-2 %3 ==0 의 경우도 고려하여 재귀함수를 작성한다.

 

코드

---

재귀

#include <iostream>
using namespace std;
int iCount = 0;

void Func(int N, int count)
{
	if (iCount != 0 && count > iCount) return;

	if (N == 1)
	{
		if (iCount == 0) iCount = count;
		if (iCount > count) iCount = count;
	}
	else
	{
		if (N % 3 == 0) Func(N/3, count+1);
		if (N % 2 == 0) Func(N/2, count+1);
		if (((N - 1) % 3 == 0) || ((N - 1) % 2 == 0)) Func(N - 1, count + 1);
		if (N>2 &&((N - 2) % 3 == 0) ) Func(N - 2, count + 2);
	}
}
 
int main()
{
	int N = 0;
	cin >> N;

	Func(N, 0);

	cout << iCount << endl;
	return 0;
}

dp(Dynamic Programming)

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX = 1000001;

int dp[MAX];
int main()
{
	int N = 0;
	cin >> N;

	dp[1] = 0;
	for (int i = 2; i <= N; i++) {
		dp[i] = dp[i - 1] + 1;
		if (i % 3 == 0)
			dp[i] = min(dp[i], dp[i / 3] + 1);
		else if (i % 2 == 0)
			dp[i] = min(dp[i], dp[i / 2] + 1);
	}

	cout << dp[N] << endl;
	return 0;
}