문제

문제 링크

동빈북으로 유명한 '이것이 코딩 테스트다' 에 part2 DP문제와 유사하다.
그리디로 접근하면 당연히 반례가 있으므로 DP로 접근하여야 한다.
각 dp테이블에 최적의 해를 찾는과정으로
1. i-1
2. 2로나뉠경우,
3. 3으로 나뉠경우,
case3가지중 최소값을 찾아서 저장하며 상향식으로 풀면된다.

또한 문제에서 1로 만드는 과정도 나열하라고 하였기때문에, before배열을 이용하여 각 연산마다 기록한다.

소스코드

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
int dp[1000001];
int used[1000001];
int main() { //dp[1] = 0;


	int N;
	int temp2;
	int temp;
	cin >> N;
	
	used[1] = -99;
	dp[1] = 0;
	
	for (int i = 2; i <= N; i++) {
		dp[i] = dp[i - 1] + 1;
		used[i] = i - 1;
		if (i % 2 == 0 && dp[i] > dp[i / 2] + 1)
		{
			dp[i] = dp[i / 2] + 1;
			used[i] = i / 2;
		}
		if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
			dp[i] = dp[i / 3] + 1;
			used[i] = i / 3;
		}
	}
	cout << dp[N] << endl;
	while (N != -99) {
		cout << N << ' ';
		N = used[N];
	}


	return 0;
}