1로 만들기 (백준 - 1463번)

동적계획법을 사용하여 푸는 문제이다.

 

우선 규칙을 먼저 살펴보자. 

 

* 정수 2

1. 1을 빼면 1이 된다.

2. 2로 나누어 떨어지고 1이 된다.

3. 3으로 나누어 떨어지지 않는다.

-> 정수 2를 1로 만드는 최소 횟수는 1이다.

 

* 정수 3

1. 1을 빼면 2가 된다. 정수 2에서 1로 되는 최소 횟수는 1이다. 그러므로 1 + 1 = 2이다.

2. 2로 나누어 떨어지지 않는다.

3. 3으로 나누어 떨어지고 1이 된다.

-> 정수 3을 1로 만드는 최소 횟수는 1이다.

 

* 정수 4

1. 1을 빼면 3이 된다. 정수 3에서 1로 되는 최소 횟수는 1이다. 그러므로 1 + 1 = 2이다.

2. 2로 나누어 떨어지고 2가 된다. 2에서 1로 되는 최소 횟수는 1이다. 그러므로 1 + 1 = 2이다.

3. 3으로 나누어 떨어지지 않는다.

-> 정수 4를 1로 만드는 최소 횟수는 2이다.

 

* 정수 5

1. 1을 빼면 4가 된다. 정수 4에서 1로 되는 최소 횟수는 2이다. 그러므로 1 + 2 = 3이다.

2. 2로 나누어 떨어지지 않는다.

3. 3으로 나누어 떨어지지 않는다.

-> 정수 5를 1로 만드는 최소 횟수는 3이다.

 

규칙을 세워보면 다음과 같다.

F(N)_1 = F(N - 1) + 1 (1을 뺐을때)

F(N)_2 = F(N / 2) + 1 (2로 나누었을때)

F(N)_3 = F(N / 3) + 1 (3으로 나누었을때)

F(N) =  F(N)_1  or  F(N)_2  or  F(N)_3  

(셋 중 가장 작은 것이 F(N)의 값으로 들어간다.)

 

이 규칙을 토대로 DP배열을 선언하여 2의 인덱스 위치부터(정수 0과 1은 항상 0이므로) 원하는 정수 값 N의 인덱스 위치까지 분기문으로 진행한다. 그 후 N의 인덱스 위치 값이 N이 1로 되기위한 최소 횟수이다.

 

코드는 다음과 같다.

#include <iostream>
using namespace std;

int min(int a, int b)
{
	return a < b ? a : b;
}

int main()
{
	int dp[1000001];
	dp[0] = dp[1] = 0;

	int input;
	cin >> input;

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

	cout << dp[input] << endl;
}