문제 링크: 1로 만들기

---

문제 풀이 과정

Dynamic Programming 문제이다.
DP를 공부하며 참고한 링크 : Dynamic Programming

이 문제를 풀면서 고민을 정말 많이했다.
DP 문제를 많이 안 풀어봐서 DP를 공부하면서 풀 겸 결국 검색해서 풀이를 보았다.
참고한 문제풀이

DP 규칙 찾기

일단 전체적으로 한번씩 적으며 dp식이 어떻게 반복되는가를 찾았다.

idx = input	calculation	dp 식
1	0	dp[1] = 0
2	2 → 1	dp[2] = 1
3	3 → 1	dp[3] = 1
4	4 → 2 → 1	dp[4] = 1+dp[i/2]
5	5 → 4 → 2 → 1	dp[5] = 1+dp[i-1]
6	6 → 3 → 1 or 6 → 2 → 1	dp[6] = 1+dp[i/3] or dp[6] = 1+dp[i/2]
7	7 → 6 → 3 → 1	dp[7] = 1+dp[i]
8	8 → 4 → 2 → 1	dp[8] = 1+dp[i/2]
9	9 → 3 → 1	dp[9] = 1+dp[i/3]
10	10 → 9 → 3 → 1	dp[10] = 1+dp[i-1]
11	11 → 10 → 9 → 3 → 1	dp[11] = 1+dp[i-1]

반드시 dp[i] = 1+dp[i-1] 은 성립한다.

이렇게 다 적고보면 규칙이 전체적으로 보인다.

1. 2로도 3으로도 안나눠지는 값
2. 2로도 3으로도 나눠지는 값
3. 2로 나눠지는 값
4. 3으로 나눠지는 값

.
.

2로도 3으로도 안나눠지는 값

위 표에서는 5, 7, 11이 될 수 있겠다.
이런 경우는 무조건 1을 뺀 후 이전 dp값을 사용하는 경우 뿐이기 때문에
dp[i] = 1+dp[i-1]

2로도 3으로도 나눠지는 값

6, 12와 같은 값!
이런 경우 2개의 경우의 수 중에 연산의 개수가 작은 것을 선택한다.
min(d[i] = 1+dp[i/2], dp[i] = 1+dp[i/3])

2로 나눠지는 값

4, 8, 10
이런 경우는 이전 값을 사용하는 dp 식과 i/2 dp식을 이용하는 것 중 작은 것을 선택
min(dp[i] = 1+dp[i-1], dp[i] = 1+dp[i/2])

3으로 나눠지는 값

9와 같은 값

min(dp[i] = 1+dp[i-1], dp[i] = 1+dp[i/3])

전체코드

#include <iostream>

using namespace std;

// variable
int dp[1000001];
int input;

int main()
{
	cin >> input;
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 2;

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

	cout << dp[input];
	return 0;
}