3장 다이나믹 프로그래밍 - (2) 문제 풀이 1 [1463번 1로 만들기]

1463번 1로 만들기

#include <iostream>

using namespace std;

int go(int n);

int d[1000001];

int main(void) {

int n;

cin >> n;

cout << go(n) << endl;

}

int go(int n) {

d[1] = 0;

int temp;

for (int i = 2; i <= n; i++) {

temp = d[i - 1] + 1;

if (i % 2 == 0 && temp > d[i / 2] + 1) {

temp = d[i / 2] + 1;

}

if (i % 3 == 0 && temp > d[i / 3] + 1) {

temp = d[i / 3] + 1;

}

d[i] = temp;

}

return d[n];

}