문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
   정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.ㅉ

풀이

코드

#include <iostream>
using namespace std;
#define MIN(a,b) (a > b ? b : a)
int dp[10000001];

int main()
{
	int i, n;
	scanf("%d", &n);
	dp[1] = 0;
	dp[2] = 1;
	for (int i = 3; i <= n; i++)
	{
		if (i % 6 == 0)
			dp[i] = MIN(MIN(dp[i / 2], dp[i / 3]), dp[i - 1]) + 1;
		else if (i % 3 == 0)
			dp[i] = MIN(dp[i / 3], dp[i - 1]) + 1;
		else if (i % 2 == 0)
			dp[i] = MIN(dp[i / 2], dp[i - 1]) + 1;
		else
			dp[i] = dp[i - 1] + 1;
	}
	cout << dp[n] << endl;
	return (0);
}

처음엔 2의 배수일 때는 i/2 배열에서 + 1을, 3의 배수일 때는 i/3 배열에서 + 1을, 나머지 경우에서는 i-1에서 + 1을 해주면 되는줄 알았는데,
힌트에서 10의 경우에서 10은 2의 배수인데 9를 이용하는 것을 볼 수 있다.
10 -> 9 -> 3 -> 1
총 3번의 연산을 사용하는데, 이 힌트를 이용해서

		else if (i % 3 == 0)
			dp[i] = MIN(dp[i / 3], dp[i - 1]) + 1;
		else if (i % 2 == 0)
			dp[i] = MIN(dp[i / 2], dp[i - 1]) + 1;
		else
			dp[i] = dp[i - 1] + 1;

의 조건문을 추가해주고, 6의 배수일 때도 있어서

		if (i % 6 == 0)
			dp[i] = MIN(MIN(dp[i / 2], dp[i / 3]), dp[i - 1]) + 1;

다음과 같은 조건문을 더해준다.