[BOJ] 12852_1로 만들기 2 with cpp

# 생각

단순히 값만 출력하는게 아니라 거쳐온 과정을 출력하라고 되어있기 때문에

경로 추적용 테이블을 추가 선언해주면 된다

 

d[k]

1	2	3	4	5	6	7	8
0	1	1	2	3	2	3	3

pre[k] (경로 추적용)

1	2	3	4	5	6	7	8
0	1	1	2	4	3	6	4

pre[3] = 1 --> 3일 때는 1로 가는게 최적이라는 뜻이다

10일 때를 생각해보면 9로 부터 왔고, 9에서는 3, 3에서는 1로

10 9 3 1 이라는 경로를 찾아낼 수 있다

 

 

# 전체 코드

#include <bits/stdc++.h>
using namespace std;

int d[1111111], pre[1111111];

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

	int n;
	cin >> n;
	for (int i = 2; i <= n; i++)
	{
		d[i] = d[i - 1] + 1;
		pre[i] = i - 1;	// 최적 경로 저장
		if (i % 2 == 0 and d[i] > d[i / 2] + 1)
		{
			d[i] = d[i / 2] + 1;
			pre[i] = i / 2;	// 최적 경로 저장
		}
		if (i % 3 == 0 and d[i] > d[i / 3] + 1)
		{
			d[i] = d[i / 3] + 1;
			pre[i] = i / 3;	// 최적 경로 저장
		}
	}
	cout << d[n] << '\n';
	while (true)
	{	// 원소 순회를 이용한 경로 출력
		cout << n << ' ';
		if (n == 1) break;
		n = pre[n];
	}
}

 

---

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

12852번: 1로 만들기 2