풀이전략

1) 처음에는 연산의 횟수를 줄여야 하므로 조건을 if / else if로 끊어서
생각했다. 그러니까 a.5로 나눌 수 있다면 5로 나누고, for문 순환 증가하고,
나머지 연산 b,c,d 조건문 끝냄.

• 하지만 이렇게 작성하면 예로 보여준 26은 성립 안된다.
  위에서 생각한대로 진행하면 1로 빼는 것은 연산의 우선순위 최하위 이므로
  26 -> 13 -> 12 -> 4 -> 2 - > 1 : 총 5번의 연산이 최소이다! 라고 생각을 하게 되는데

• 예에서는 26 -> 25 -> 5 -> 1 이므로
  위의 1)번 생각이 잘못됨을 증명할 수 있다.

끄적끄적

-> if~ else if~ 로 구분하는 것이아니라 조건을 따로 규정지으면서
그 중에서도 최소 연산을 찾아야 하겠다 판단할 수 있다.

점화식을 만들어보자.

: n을 1로 만들어 낼수 있는 최소한의 연산 갯수는?
dp[n] = dp[n / 5] + 1;
-> 여기서 +1은 연산 한번이 진행되었다라는 것을 나타낸다.

dp[n] = dp[n / 5] + 1;
dp[n] = dp[n / 3] + 1;
dp[n] = dp[n / 2] + 1;
dp[n] = dp[n - 1] + 1;

이렇게 표현할 수 있다. 그리고 예외처리를 추가하자.

최소 연산이므로 각 dp[n] 연산을 하면서 min 값을 갱신하면 된다.

소스코드

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


int main() {

	int n;
	cin >> n;

	vector<int>dp(n + 1, 0);

	dp[1] = 0;
	
	for (int i = 2; i <= n; i++)
	{
		dp[i] = dp[i - 1] + 1;

		if (i % 5 == 0)
		{
			dp[i] = min(dp[i / 5] + 1,dp[i]);
		}
		
		if (i % 3 == 0)
		{
			dp[i] = min(dp[i / 3] + 1, dp[i]);
		}

		if (i % 2 == 0)
		{
			dp[i] = min(dp[i / 3] + 1, dp[i]);
		}
	}
	cout << dp[n];
	return 0;
}