下呂数

gero-number.cc

#include <climits>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int input = 0;
  cin >> input;

  vector<int> steps(input+1);
  vector<int> prev(input+1);
  steps[0] = 0;
  prev[0] = -1;
  steps[1] = INT_MAX;
  prev[1] = -1;
  steps[2] = 1;
  prev[2] = 0;
  steps[3] = 1;
  prev[3] = 0;
  for (int i = 4; i <= input; ++i) {
    if (steps[i-2] < steps[i-3]) {
      steps[i] = steps[i-2] + 1;
      prev[i] = i-2;
    }
    else {
      steps[i] = steps[i-3] + 1;
      prev[i] = i-3;
    }

    if (i % 2 == 0 && steps[i/2] < steps[i]) {
      steps[i] = steps[i/2] + 1;
      prev[i] = i/2;
    }
    if (i % 3 == 0 && steps[i/3] < steps[i]) {
      steps[i] = steps[i/3] + 1;
      prev[i] = i/3;
    }
  }

  cout << steps[input] << endl;
  cout << "---" << endl;
  int cur = input;
  while (true) {
    cout << cur << endl;
    if (cur == 0) {
      break;
    }
    cur = prev[cur];
  }

  return 0;
}