[1463] 1로 만들기

---

동적계획법으로 해결한 문제다. 먼저 Table[i] -> i를 1로 만드는데 주어진 3가지 연산을 사용하는 횟수의 최솟값 이라고 정의한다.

1부터 차례대로 예를 들어가면서 문제를 파악해보자. Table[1] = 0이다.

2 -> 1 이므로 Table[2] = 1

3 -> 1 이므로 Table[3] = 1

4 -> 2 -> 1 과 4 -> 3 -> 1 두가지 경우가 있는데, 둘다 2번 연산하므로 Table[4] = 2 이다. 

근데 자세히 보면 Table[4] = Table[2] + 1 이나 Table[3] + 1로 표현할 수 있다.

5 -> 4 -> 2 -> 1 과 5 -> 4 -> 3 -> 1 두가지 경우가 있는데 3번 연산을 하므로 Table[5] = 3 이다.

Table[5] = Table[4] + 1 로 표현할 수 있다. 이런식으로 진행하다보면 규칙이 보인다.

10을 마지막 예로 들자면 10 -> 5 -> 4 -> 3 -> 1 과 10 -> 9 -> 3 -> 1 등 여러가지 경우가 있는데

 Table[10] 에서는 후자인 3이 답이다.

그래서 우리가 Table을 한개씩 채워가면서 봐야할 것은 1,2,3은 초항값으로 1을 넣어주고

4부터 Table[i] = Table[i-1] + 1 의 값과 만약에 i가 3 으로 나누어 떨어진다면 Table[i/3], 2로 나누어 떨어진다면 Table[i/2] 의 값을

비교해서 둘중 최솟값을 Table[i] 값으로 정해야 한다는 규칙을 발견할 수 있다.