백준 1463 - 1로 만들기

3으로 나누어 떨어지면 3으로 나누기, 2로 나누어 떨어지면 2로 나누기, 1 빼기 연산을 통해 1을 만들 수 있는 최소한의 연산 수를 구하는 문제입니다.

연산 개수를 1부터 차례대로 보면 다음과 같이 표로 만들 수 있습니다.

value	cnt
1	0
2	1
3	1
4	2
5	3
6	2
7	3
8	3
9	2
10	3
11	4
12	3

12을 예시로 설명하겠습니다.
12을 1로 만드는 연산 개수를 3가지 경우를 통해 산출할 수 있습니다.

• 1을 뺀다.
  1을 빼면 11이므로 11의 연산 개수에 1을 더하면 5가 나옵니다.
• 2로 나눈다.
  2로 나누면 6이므로 6의 연산 개수에 1을 더하면 3이 나옵니다.
• 3으로 나눈다.
  3으로 나누면 4이므로 4의 연산 개수에 1을 더하면 3이 나옵니다.
  

위 세가지 경우 중 가장 작은 수가 1을 만드는 가장 작은 연산 개수가 됩니다.

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
	int X;
	std::cin >> X;

	std::vector<int> cnts(X + 1);
	
	cnts[1] = 0;
	cnts[2] = 1;
	cnts[3] = 1;


	for (int i = 4; i <= X; i++)
	{
		cnts[i] = cnts[i - 1] + 1;
		if (i % 3 == 0) cnts[i] = std::min(cnts[i], cnts[i / 3] + 1);
		if (i % 2 == 0) cnts[i] = std::min(cnts[i], cnts[i / 2] + 1);
	}

	std::cout << cnts[X];

	return 0;
}