1463 1만들기

브루트포스로 풀릴것 같은데 왠지 시관초과가 날 것 같다. 

꼭 다시 재귀방법으로 풀어보기로.

변수 정의를 잘 해야겠다.

D[x] 를 "x를 1로 만드는데 필요한 최소한의 연산 횟수" 라고 정의한다면 문제가 쉬워진다.

코드:

#include <iostream>

using namespace std;

int D[1000001];

int main()

{

int X;

cin >> X;

D[1] = 0;

D[2] = D[3] = 1;

int temp = 0;

for (int i = 4; i <= X; i++)

{

D[i] = D[i - 1] + 1;

if (i % 2 == 0){

temp = D[i / 2] + 1;

if (temp < D[i]){

D[i] = temp;

}

}

if (i % 3 == 0){

temp = D[i / 3] + 1;

if (temp < D[i]){

D[i] = temp;

}

}

}

cout << D[X];

return 0;

}