[ DP - 1463 ] 1로 만들기(C++)

접근법

점화식을 이끌어 내야 하는 중요한 문제이다.

단순히 3으로 나눠지고 2로 나눠진다고 해서 해당 값으로 나누는 연산을 진행 시 최소값을 찾을 수 없게 된다.

이러한 DP문제는 직접 규칙을 찾아보는 것이 가장 중요하다.

 

 

연산이 가능한 것을 고려하였을 때 2와 3은 1번의 연산으로 1로 만들 수 있다. 이는 1일 때는 1로 만드는데 0번의 연산이 걸리는 점을 고려하고 넘어가자.

 

4는 2로 나누어 떨어지기에 2로 나눈 값인 2는 1번의 연산이 더 필요하다.

또한, 1을 먼저 빼고 3으로 나누어도 동일하게 1로 만들 수 있다.

 

5는 2와 3 모두 나누어 떨어지지 않는다. 따라서 1을 뺀 후 4는 2가지 방법으로 총 2번의 연산을 통해 1로 만들 수 있다.

 

6은 2와 3으로 모두 나누어 떨어진다. 2로 나누면 3이고, 3은 1번의 연산으로 1로 만들 수 있다.

혹은 1을 먼저 빼고 난 값이 5이고, 5는 다시 1을 뺀 후 4로 만들어 4에서 1로 가는 2번의 연산을 진행하면 1로 만들 수 있다. 하지만 최소값은 2와 3 모두로 나누어 떨어지기에 둘 중 하나의 값으로 나누는 연산 과정에서 구할 수 있다.

 

여기서 규칙을 찾아보자면 오른쪽 형광색을 주의깊게 살펴보자. 2 혹은 3으로 나누어 떨어지면, 해당 값으로 나눈 후 각 값에서 요구되는 횟수 + 1의 연산이 최종적으로 요구된다.

만약 나누어 떨어지지 않는다면, 1을 뺀 값에 대한 연산 횟수 + 1의 연산이 최종적으로 요구된다.

 

이를 수식적으로 표현 해 보자. 각 숫자에 따른 연산 횟수를 DP라는 배열에 저장되어 있다고 해 보자.

 

$DP[2] = DP[1] +1$

$DP[3] = DP[1] +1 , DP[3] = DP[2] + 1 ->$ 이 둘 중 더 작은 값이 최종적인 결과이다.

$DP[4] = DP[4/2] + 1$

$DP[5] = DP[5-1] + 1$

 

이렇게 표현하면 점화식을 충분히 세울 수 있을 것이다. 3에 대해서는 2가지 방법이 있다. 3으로도 나누어 떨어지지만, 1을 뺀 값에 대한 연산 횟수에서 +1을 한 경우. 따라서 이 모든것을 고려한 후 최소값을 찾아야 한다.

 

따라서 전체적인 알고리즘은 먼저 1을 뺀 값에 대한 연산 횟수 + 1로 연산 횟수를 설정하고, 2와 3으로 나누어 떨어지는 경우에 대해여 연산 횟수를 비교하여 최소값을 찾으면 된다.

 

---

정답

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

int32_t ars32_DP[1000000];

int main()
{

	int32_t s32_Input, s32_I;

	cin >> s32_Input;

	ars32_DP[1] = 0;

	for (s32_I = 2; s32_I <= s32_Input; s32_I++)
	{
		// 1 빼기
		ars32_DP[s32_I] = ars32_DP[s32_I - 1] + 1;

		if (s32_I % 3 == 0)
		{
			ars32_DP[s32_I] = min(ars32_DP[s32_I], ars32_DP[s32_I / 3] + 1);
		}

		if (s32_I % 2 == 0)
		{
			ars32_DP[s32_I] = min(ars32_DP[s32_I], ars32_DP[s32_I / 2] + 1);
		}
	}

	printf("%d\n", ars32_DP[s32_Input]);

	return 0;
}