[백준 1463] 1로 만들기

주어진 숫자( N )에서 세가지 연산을 하는데,

만약, N이 3으로 나누어 떨어지면 N-3, N이 2로 나누어 떨어지면 N-2

아니면, 언제든지 -1을 빼서 N-1을 만들수도 있다.

 

예를 들어, N = 10 인 경우,

 

9 or 5 가  될 수 있고

 

N = 9 인 경우, 8 or 3 이 될 수 있다.

 

따라서, 이런 방법으로 주어진 숫자를 1로 만드는 최소연산횟수를 구하는 문제였다. 

 

- 풀이법

 

DP[N] : 숫자 N 인 경우를 기록한다.

 

그럼, 점화식은

if( N 이 2로 나누어질 경우 )

   DP[N] = min(1 + DP[N/2, 1 + DP[N-1])

else if( N 이 3으로 나누어질 경우)

   DP[N] = min(1 + DP[N/3], 1 + Dp[N-1])

else N 이 2 나 3으로 나누어지지 않을 경우

   DP[N] = DP[N-1] + 1

 

위와 같은 점화식을 기반으로 Top-Down 방식으로 문제를 접근하면 풀이가 가능하다.

#include <iostream>
#include <algorithm>

#define MAX	1000000

using namespace std;

int dp[MAX + 1];
int n;

int go(int n)
{
	if (n == 1)
		return 0;

	int& ret = dp[n];
	if (ret != 0) return ret;

	if (n % 3 == 0 && n - 1 > 0) 
	{
		ret = min(1 + go(n - 1), 1 + go(n / 3));
	}
	else if (n % 2 == 0 && n - 1 > 0)
	{
		ret = min(1 + go(n - 1), 1 + go(n / 2));
	}
	else
	{
		ret = 1 + go(n - 1);
	}

	return ret;
}

int main()
{
	cin >> n;

	cout << go(n) << endl;

	return 0;
}