• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jul 16th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <string>
3.
4. using namespace std;
5.
6. //int calculate(int N);
7. int dp[100];//dp[i] : i를 1로 만들기 위한 최소한의 연산 횟수
8.
9. int main() {
10.     int N;
11.
12.     cin >> N;
13.     dp[1] = 0;
14.
15.     for (int i = 2; i <= N; i++) {
16.         dp[i] = dp[i - 1] + 1;
17.
18.         if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
19.             dp[i] = dp[i / 2] + 1;
20.         }
21.         if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
22.             dp[i] = dp[i / 3] + 1;
23.         }
24.     }
25.     cout << dp[N];
26.     //cout << calculate(N);
27.
28.     return 0;
29. }
30.
31. /*int calculate(int N) {
32.
33.     if (N == 1) {
34.         return 0;
35.     }
36.     else if (N % 3 == 0) {
37.         if (calculate(N / 3) < calculate(N - 1)) {
38.             dp[N] = calculate(N / 3) + 1;
39.         }
40.         else {
41.             dp[N] = calculate(N - 1) + 1;
42.         }
43.         return dp[N];
44.     }
45.     else if (N % 2 == 0) {
46.         if (calculate(N / 2) < calculate(N - 1)) {
47.             dp[N] = calculate(N / 2) + 1;
48.         }
49.         else {
50.             dp[N] = calculate(N - 1) + 1;
51.         }
52.         return dp[N];
53.     }
54.     else {
55.         dp[N] = calculate(N - 1) + 1;
56.         return dp[N];
57.     }
58.
59. }*/
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top