[BOJ] 12852 1로 만들기 2

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

12852번: 1로 만들기 2

알고리즘: DP, DFS

 

시간복잡도: O(logN)

 

 

1463 1로 만들기에서 경로 추적을 추가한 문제.

https://moon323.tistory.com/5

 

접근:

Dp 경로 추적 문제들이 늘 그렇듯 점화식에서 참고한 부분문제의 성분을 저장해주면 됨.

 

ex)

v[] : 경로 추적 배열

D[X] = Min(D[X/2] + X%2 + 1, D[X/3] + X%3 +1) 에서

D[X/2] 부분을 가져왔으면 v[X] = 2로 표시, D[X/3] 부분을 가져왔으면 v[X] = 3 으로 표시

 

v를 참고하여 역추적하면서 만약 나누어 떨어지지 않으면 나누어 떨어질 때까지 -1씩 해서 출력하면 됨.

 

예제: 10

X: 10 -> 9 -> 3 -> 1

v:  3, 3, 3, 0 (0: 끝나는 지점 표시)

 

1. v[10] = 3, 10은 3으로 안나누어 떨어짐-> 1씩 감소하면서 출력

output: 10, 9

2. v[9] = 3, 9는 3으로 나누어 떨어짐

output: 3

3. v[3] = 3, 3은 3으로 나누어 떨어짐

output: 1

4. v[1] = 0 end.

 

 

#include <iostream>
using namespace std;
int N, v[1000001], p;
int f(int n)
{
	int a, b;
	
	if (n <= 1)
		return 0;
	a = f(n/3) + n%3 + 1;
	b = f(n/2) + n%2 + 1;
	
	if (a > b)
	{
		v[n] = 2;
		return b;
	}
	else
	{
		v[n] = 3;
		return a;
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	cout << f(N) << endl;
	
	p = N;
	while (p > 1)
	{
		for (int i = p; i >= p-p%v[p]; i--)
			cout << i << " ";
		p /= v[p];
	}
	cout << 1;
	return 0;
}