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

문제 링크: https://www.acmicpc.net/problem/12852

 

dp 역추적 문제입니다. 1로 만들기라는 문제에 역추적만 추가된 버전입니다.

이전값으로 가는 값을 배열을 만들어주고 업데이트 해주면 됩니다

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


int dp[1000001];
int before[1000001];

int solve(int x) {
	dp[1] = 0;
	before[1] = -1;

	for (int i = 2; i <= x; ++i) {
		dp[i] = dp[i - 1] + 1;
		before[i] = i - 1;

		if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
			dp[i] = dp[i / 2] + 1;
			before[i] = i / 2;
		}
		if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
			dp[i] = dp[i / 3] + 1;
			before[i] = i / 3;
		}
	}

	return dp[x];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	cin >> n;
	cout << solve(n) << '\n';
	
	while (n != -1) {
		cout << n << ' ';
		n = before[n];
	}
	cout << '\n';

	return 0;
}

바텀업 방식으로 풀었습니다