[BOJ] 12852번 : 1로 만들기 2

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n;
int d[1000005]; 
int pre[1000005]; 
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n;
	d[1] = 0; 

	for (int i = 2; i <= n; i++) {
		d[i] = d[i - 1] + 1;
		pre[i] = i - 1;
		if (i % 2 == 0 && d[i] > d[i/2] + 1) {
			d[i] = min(d[i], d[i / 2] + 1);
			pre[i] = i / 2;
		}
		if (i % 3 == 0 && d[i] > d[i/3] + 1) {
			d[i] = min(d[i], d[i / 3] + 1);
			pre[i] = i / 3;
		}
	}
	cout << d[n] << '\n';
	int cur = n; 
	while (true) {
		cout << cur << ' '; 
		if (cur == 1) break; 
		cur = pre[cur];
	}
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/12852.cpp

basic-algo-lecture/0x10/solutions/12852.cpp at master · encrypted-def/basic-algo-lecture