2강. 문제풀이1_1로 만들기,

BFS로도 가능할 것 같은데??

D[n]에 어떤 값이 저장되어야하는지 먼저 정해야함.

문제에서 구하라고 하는 내용을 그대로 넣어주면 됨.

D[n] = N을 1로 만드는데 필요한 연산의 최소값.

N-> ... -> 1 : D[n]번의 연산 사용한 것.

1) 나누기 3을 할 경우, 연산 과정에서 연산 횟수는, 1(나누기 3)과 D[N/3] 부분으로 나뉨.

2) 나누기 2 : 1(나누기 2)과 D[N/2] 부분으로 나뉨.

3) 빼기 1 : 1(빼기 1)과 D[N-1]부분으로 나뉨.

D[n/3] : N/3을 1로 만드는 데 필요한 연산의 최소값.

D[n] 을 만드는 방법은 총 세가지 이므로

D[n] = D[n/3] + 1

D[n] = D[n/2] + 1

D[n] = D[n-1] + 1

즉, 이 중 최소값을 구하면 됨.

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