백준 1463번 : 1로 만들기 (DP)

문제

 

 

C++

#include <bits/stdc++.h>
using namespace std;
int d[1000005];
int n;
int main(void) {
  cin >> n;
  d[1] = 0;
  for(int i = 2; i <= n; i++){
    d[i] = d[i-1]+1;  // 1을 빼는  경우 : 
    if(i%2 == 0) d[i] = min(d[i],d[i/2]+1);  // 2를 나누는 경우 
    if(i%3 == 0) d[i] = min(d[i],d[i/3]+1);  // 3를 나누는 경우 
  }
  cout << d[n];
}