Create 12852.cpp

encrypted-def · web-flow · commit 75cbbed3f3c9 · 2021-01-28T03:33:09.000+09:00
diff --git a/0x10/12852.cpp b/0x10/12852.cpp
@@ -0,0 +1,33 @@
+// http://boj.kr/da0497aabb26436c9ae613785cb439f7
+#include <bits/stdc++.h>
+using namespace std;
+
+int d[1000005];
+int pre[1000005];
+int n;
+
+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] = d[i/2] + 1;
+      pre[i] = i/2;
+    }
+    if(i%3 == 0 && d[i] > d[i/3] + 1){
+      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];    
+  }
+}
