🐣 문제

링크 : https://www.acmicpc.net/problem/1463

🐥 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dy[1000001];

void dp(int n){
  dy[1] = 0;

  for(int i = 2; i <= n; i++){
    if(i % 2 != 0 && i % 3 != 0)
      dy[i] = dy[i-1] + 1;
    if(i % 2 == 0 && i % 3 == 0)
      dy[i] = min(dy[i/2] + 1, dy[i/3] + 1);
    else if(i % 2 == 0 )
      dy[i] = min(dy[i/2] + 1, dy[i-1] + 1);
    else if(i % 3 == 0)
      dy[i] = min(dy[i/3] + 1, dy[i-1] + 1);
  }
}

int main(){
  int n;
  cin >> n;
  
  dp(n);

  cout << dy[n];
  
  return 0;
}