기본적인 dp문제, 재귀를 통하여 해결했습니다.
설명은 주석처리했습니다.
|
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>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
using namespace std;
typedef long long ll;
ll dp[1000001];
ll dfs(ll num) {
if (num == 1) return 1;
if (num <= 1000000) {
ll& res = dp[num];
if (res) return res;
ll ans = 0;
if (num % 2) ans += dfs(num * 3 + 1) + 1;
else ans += dfs(num / 2) + 1;
return res = ans;
}
else {
ll ans = 0;
if (num % 2) ans += dfs(num * 3 + 1) + 1;
else ans += dfs(num / 2) + 1;
return ans;
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// 0 < n < 1000000 의 두 쌍 i, j가 주어지면
// i부터 j까지의 모든 수 중 a가 1이 되기 위해 거쳐야하는 과정의 사이클 이 가장 많은 수를 출력한다.
/*
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ..
1 -> 1
2 -> 2 1
3 -> 3 10 5 16 8 4 2 1
4 -> 4 2 1
.. dp
*/
// 100만까지는 무조건 1로 수렴가능하다고 했다
// 만약 100만을 넘어서는 수가 있으면 memory로 해결할 수 없으니 직접 재귀를 돌린다.
for (int i = 1; i < 1000001; i++)
dp[i] = dfs(i);
int i, j;
while (1) {
int a, b;
cin >> i >> j;
if (cin.eof()) break;
a = i, b = j;
if (i > j) swap(i, j);
ll ans = 0;
for (int k = i; k <= j; k++) ans = max(ans, dp[k]);
cout << a << " " << b << " " << ans << "\n";
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > uva' 카테고리의 다른 글
| uva 10150번 Doublets (0) | 2020.03.27 |
|---|---|
| uva 10469번 To Carry or not to Carry (0) | 2020.03.23 |
| uva 10010번 Where's Waldorf? (0) | 2020.03.23 |
| uva 679 - Dropping Balls (0) | 2020.03.19 |
| uva 10137 - the trip, BOJ 4411번 (0) | 2020.03.19 |