[백준 1463] 1로 만들기

1463번: 1로 만들기 (acmicpc.net)

1463번: 1로 만들기

 

배운 것

 

출처 : BaaaaaaaarkingDog | [실전 알고리즘] 0x10강 - 다이나믹 프로그래밍 (encrypted.gg)

 

 

정답 코드

#include <bits/stdc++.h>
using namespace std;

int d[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;
    if(i%2 == 0) d[i] = min(d[i],d[i/2]+1);
    if(i%3 == 0) d[i] = min(d[i],d[i/3]+1);
  }
  cout << d[n];
}