🖊️ 문제

https://www.acmicpc.net/problem/1463

---

🖊️ 풀이

dp는 정말 언제 풀어도 어렵다 후앵
실버3맞냐고요...

문제도 짧고 코드도 짧지만..
점화식 세우는게 어렵다.

조건
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

세 연산의 사용 횟수의 합의 최솟값 구하기.

일단 생각해보면

1 = 0 (무조건 1임)
2 = 2 -> 1 (빼든, 2로 나누든 1)
3 = 3 -> 2 -> 1 / 3->1
4 = 4 -> 2 -> 1 / 4 -> 3 -> 1
5 = 5 -> 4 -> 2 -> 1 / 5 -> 4 -> 3 -> 1
6 = 6 -> 3 -> 1 / 6 -> 2 -> 1 / 6 -> 5 -> ...
7 = 7 -> 6-> ...
8 = 8 -> 4 -> ... / 8 -> 7 -> ...
9 = 9 -> 3 -> 1 / 9 -> 8 -> ..

...

몇 개 해보다보면 규칙을 알겠다

n에 대한 연산의 최솟값은
1. n-1에 대한 연산 + 1
2. 3으로 나누어진다면 -> n/3에 대한 연산 + 1
3. 2로 나누어진다면 -> n/2에 대한 연산 + 1

위 세 가지 경우의 수 중에 최소가 원하는 값이 된다.

그래서
각 연산에 대해
점화식을 세우면

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);
    if (i % 2 ==0) dp[i] = min(dp[i], dp[i/2] + 1);
}

이렇게 된다.
위에 한글로 적은 식을 그대로 코드로 옮긴거다.

점화식만 세우면 코드는 쉬운게 dp의 특징 .. 흐규

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

int dp[1'000'001];

int main()
{
	int n;
	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);
		if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1);
	}
	cout << dp[n] << endl;
}