백준 1463 1로 만들기

일단 3으로, 2로 모두 나누어 떨어지면 3으로 나누는 것이 최소값을 구할 수 있는 방법일까? 2로 나눠야 최소값이 나오는 경우도 있지 않을까?

그리고 3으로 나누어 떨어지는 홀수를 3으로 바로 안 나누고 1을 뺀 후에 2로 나누는 경우가 3으로 바로 나누는 경우보다 나을 수도 있지 않을까?

위의 사항들에 대해서... 확실하게 어떤 것이 최적이다라고 증명을 할 수 있으려나...
일단 증명을 안 한다면 모든 경우를 다 해보는 방식으로 dp를 적용해서 풀어도 된다.

-------------------------------------------------------

1. x가 3으로 나누어 떨어지면 3으로 나눈다.
2. x가 2로 나누어 떨어지면 2로 나눈다.
3. 1을 뺀다.

d[n] = 정수 n에 세가지의 연산을 적절히 사용해서 1을 만들기 위해 연산을 사용하는 횟수의 최소값.

d[n] = min(d[n / 3], d[n / 2], d[n - 1]) + 1;