Do you believe in you?

[문제]https://www.acmicpc.net/problem/1463정수 x 가 주어졌을 때, x 를 1로 만드는 최소 연산의 수를 찾는 문제이다. x 를 1로 만드는 연산은 3가지가 있다. 1) x 가 3 으로 나누어 떨어지면 x 를 3 으로 나눈다.2) x 가 2 로 나누어 떨어지면 x 를 2 로 나눈다.3) 1)2) 가 아니면 x 에서 1을 뺀다. 정수 x 값의 범위는 1 ≤ x ≤ 10^6 이다.제한시간은 0.15초 이다. [풀이]정수 x 의 최대값이 10^6 이기 때문에 O(n^2) 만 되어도 문제의 제한시간을 넘긴다. 즉, 완전탐색으로 풀면 안된다. 점화식을 찾아야 한다.'D[x] = x를 1로 만드는 최소 연산의 수' 라고 두고 D[1] 부터 구해보자. D[1] = 1D[2] = D[2/..

* DP(Dynamic Programming)란 ?: 큰 문제를 작은문제로 나누고 작은문제로 큰문제를 푸는 방법. 작은문제가 중복된다.(vs 분할정복: 분할정복과 비슷한데 분할정복은 작은문제가 중복되지 않는다.)  * DP 의 특징1) Overlapping Subproblem: 부분문제(작은문제)가 겹친다.2) Optimal Substructure: 최적 부분 구조. 문제의 정답을 작은 문제의 정답에서 구할 수 있다. 정답의 작은 문제의 정답은 항상 같다.  * DP 알고리즘으로 풀 수 있는 대표적인 예: 피보나치 수 !0 1 1 2 3 5 8 13 21 34 55 89 ...F0 = 0F1 = 1...Fn = Fn-1 + Fn-2(n ≥ 2)Fn 이라는 큰문제 값을 Fn-1 과 Fn-2 의 작은 합으로..