-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathdynamic1463.cpp
More file actions
72 lines (68 loc) · 1.75 KB
/
dynamic1463.cpp
File metadata and controls
72 lines (68 loc) · 1.75 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
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)