#include int d[1000001]; using namespace std; // 1로 만들기 // N을 1로 만드는 **최소** 연산 횟수 // 3으로 나누는 것이 빠르므로, 2보다 3을 먼저 나눈다. -- 그리디 알고리즘. 예외. // ** 점화식의 정의를 세워보자 ** // D[N] : N을 작게 만들 수 있는 방법 // 큰문제 단계와 나머지 다시 전체 문제로 나누면 좋다. // N -> N/3 (1번) 과 N/3 -> 1 (D[N/3]) // N -> N/2 (1번) 과 N/2 -> 1 (D[N/2]) // N -> N-1 (1번) 과 N-1 -> 1 (D[N-1]) // D[N] = min(D[N/3], D[N/2], D[N-1]) // D[1] = 0 // 1->1 //--------- TOP DOWN ----------// // n에서부터 내려가면서.. 재귀호출 int go(int n) { if (n == 1) return 0; if (d[n] > 0) return d[n]; // memoization 기억하고 있는 건 그대로 사용 // D[n-1] : **아무때나** 가능함으로, 아무때나 를 먼저 해서, **비교의 기준**으로 만들어준다. d[n] = go(n - 1) + 1; // D[n/2] if (n % 2 == 0) { int temp = go(n / 2) + 1; if (d[n] > temp) d[n] = temp; } // D[n/3] if (n % 3 == 0) { int temp = go(n / 3) + 1; if (d[n] > temp) d[n] = temp; } return d[n]; } int main() { int n; cin >> n; // cout << go(n) << '\n'; //--------- BOTTOM UP ----------// d[1] = 0; for (int i = 2; i <= n; i++) { d[i] = d[i - 1] + 1; if (i % 2 == 0 && d[i] > d[i / 2] + 1) { d[i] = d[i / 2] + 1; } if (i % 3 == 0 && d[i] > d[i / 3] + 1) { d[i] = d[i / 3] + 1; } } cout << d[n] << '\n'; return 0; } // 시간 복잡도 // 함수의 호출 횟수 * 함수의 시간 복잡도 // - 문제의 개수 - -문제 1개 푸는데 필요한 시간- // 점화식: D[N] = min(D[N/3], D[N/2], D[N-1]) // N * O(1) // 따라서 시간 복잡도: O(n)