[백준 12852] 1로 만들기 2 (C++)

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

12852번: 1로 만들기 2

문제

---

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

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

---

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

 

출력

---

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

둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

 

문제 풀이

---

dp 또는 bfs 문제.

dp 방식으로 푼 풀이 방식을 기술한다.

 

반대로 1부터 시작하여 N까지 1을 더하거나, 2를 곱하거나, 3을 곱하는 연산을 최소 몇번을 해야하는지를 구하면 된다. 

연산의 최소 횟수를 저장하는 배열 counts과 연산 이전 값을 저장하는 prev 배열을 생성하였다.

1은 연산이 필요없으므로 counts[1]에는 0이 저장된다. 그 다음은 N까지 반복문을 돌리면서 counts[i]와 prev[i]를 채운다.

 

만약 i가 2로 나누어 떨어지고 3으로도 나누어 떨어진다면 i-1로부터 온 것, i/2로부터 온 것, i/3으로부터 온 것 중 횟수가 가장 작은 것을 선택해야 한다.

i가 3으로 나누어떨어지지는 않지만 2로 나누어떨어진다면 i-1로부터 온 것과 i/2로부터 온 것 중 가장 작은 것을 선택해야 한다.

i가 2으로 나누어떨어지지는 않지만 3로 나누어떨어진다면 i-1로부터 온 것과 i/3로부터 온 것 중 가장 작은 것을 선택해야 한다.

만약 위의 경우 모두 해당 되지 않는다면 i는 i-1에서 1을 더해 값을 만들 수 있다. 따라서 counts[i]=counts[i-1]+1과 prev[i]=i-1이 성립한다.

 

아래는 코드.

나누어떨어지는 조건을 검사하기 전 counts[i]를 counts[i-1]+1로 채우고, prev를 i로 채워놓으면 나누어 떨어지는 조건에서 i-1이 최소일 때 prev를 채워넣지 않아도 되므로 앞으로 뺐다.

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int* counts = new int[N + 1];
	int* prev = new int[N + 1];
	int current = N;
	counts[0] = 0;
	counts[1] = 0;
	prev[1] = 0;
	for (int i = 2; i < N + 1; i++)
	{
		counts[i] = counts[i - 1] + 1;
		prev[i] = i - 1;
		if (i % 3 == 0 && i % 2 == 0)
		{
			counts[i] = min({ counts[i / 3]+1, counts[i / 2]+1, counts[i] });
			if (min({ counts[i / 3] + 1, counts[i / 2] + 1, counts[i] }) == counts[i / 3] + 1)
			{
				prev[i] = i / 3;
			}
			else if (min({ counts[i / 3] + 1, counts[i / 2] + 1, counts[i] }) == counts[i / 2] + 1)
			{
				prev[i] = i / 2;
			}
		}
		else if (i % 3 == 0)
		{
			counts[i] = min(counts[i / 3] + 1, counts[i]);
			if (min(counts[i / 3] + 1 , counts[i]) == counts[i / 3] + 1)
			{
				prev[i] = i / 3;
			}
		}
		else if (i % 2 == 0)
		{
			counts[i] = min(counts[i / 2]+ 1 , counts[i]);
			if ( min(counts[i / 2] + 1, counts[i]) == counts[i / 2]+1 )
			{
				prev[i] = i / 2;
			}
		}
	}
	cout << counts[N] << "\n";
	while (current != 0)
	{
		cout << current << " ";
		current = prev[current];
	}
	return 0;
}