1463 : Make it '1' (Dynamic Programming) [C,C++]

This problem can be solved easily if the condition is classified.

The conditions are classified into four categories,

Condition 1: Determine the number of squares. 9 is 2 for 3, 27 is 3 for 3, and the difference in output is 1.

Condition 2: Determining the multiple. If the number is divided by 3 or 2, divide it by + 1.

Condition 3: Initialization. 6 is a multiple of 2 and 3. If you do not initialize, condition 2 causes an error.

Condition 4: The minimum value comes out of the number of times (+ 1) and the number of the conditions 1, 2, and 3.

If you fill the array based on the above four conditions, you can easily get the output value.

--------------------------------------------------------------
//Condition 3
CalcTimes[0] = 0; CalcTimes[1] = 0; CalcTimes[2] = 1;
CalcTimes[3] = 1; CalcTimes[4] = 2; CalcTimes[5] = 3;
CalcTimes[6] = 2;
 
for (int Num = 7; Num <= nInput; Num++)
{
Least = MAX_SIZE;

//Condition 1,2
if ((Num % 3) == 0)
{
if (Least >= CalcTimes[Num / 3] + 1)
        Least = CalcTimes[Num / 3] + 1;
}
else if ((Num % 2) == 0)
{
if (Least >= CalcTimes[Num / 2] + 1)
Least = CalcTimes[Num / 2] + 1;
}

//Condition 4
        if (Least >= CalcTimes[Num - 1] + 1)
Least = CalcTimes[Num - 1] + 1;

        CalcTimes[Num] = Least;
}
--------------------------------------------------------------
<pseudo code>

*Source of the problem = https://www.acmicpc.net/problem/1463

*문제 출처 : BAEKJOON ONLINE JUDGE