1로 만들기 2

문제 링크

발상

1로 만들기 문제에 경로 추적 기믹이 추가된 문제다. 구조상 1차원 문제이므로 고민할 부분이 적다. 경로 추적을 위해서는 최적값을 구했을 때 그 이전 값을 쌍으로 저장해두면 된다.

점화식

이전 문제와 점화식은 동일하다.

$$\{\begin{array}{l}{n}_i=\text{i를 만드는데 필요한 최소 연산 횟수}\end{array}$$ $$n_i=\min (n_{i+1},n_{2i},n_{3i})+1$$

역추적

10의 경우, 답은 $10\to 9\to 3\to 1$이 된다. $3$을 탐색할 때 $3$을 도출하기 이전 수인 $4$, $6$, $9$ 중 $9$가 선택되었을 것이다. 이 $9$를 연산 횟수와 함께 저장하고 역추적할 때 사용할 수 있다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
	int c, p;
};
int main() {
	int n; cin >> n; vector<node> dp(n + 1, { (int)21e8, -1 });
	dp[1] = { 0, -1 };
	for (int i = 2; i <= n; i++) {
		node s1 = dp[i - 1].c != -1 ? dp[i - 1] : node{ (int)21e8, (int)21e8 };
		if (s1.c + 1 < dp[i].c) {
			dp[i].c = s1.c + 1;
			dp[i].p = i - 1; // 이전 수 저장
		}
		node s2 = i % 2 == 0 && dp[i / 2].c != -1 ? dp[i / 2] : node{ (int)21e8, (int)21e8 };
		if (s2.c + 1 < dp[i].c) {
			dp[i].c = s2.c + 1;
			dp[i].p = i / 2; // 이전 수 저장
		}
		node s3 = i % 3 == 0 && dp[i / 3].c != -1 ? dp[i / 3] : node{ (int)21e8, (int)21e8 };
		if (s3.c + 1 < dp[i].c) {
			dp[i].c = s3.c + 1;
			dp[i].p = i / 3; // 이전 수 저장
		}
	}
	cout << dp[n].c << "\n";	
	for (int i = n; i != 1;) { // n부터 역추적
		cout << i << " ";
		i = dp[i].p; // 현재 수 이전의 수를 찾아감
	}
	cout << 1;
	return 0;
}