Algorithm/알고스팟

algospot - pi

jhg0406 2020. 2. 2. 20:11
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
//algospot - pi
 
#include <iostream>
#include <vector>
using namespace std;
 
#define INF 100000
 
string s;
int len;
vector<int> cache;
int dp(int idx);
 
void init()
{
    cin >> s;
    len = s.size();
    cache = vector<int>(len, -1);
}
 
int case1(int start, int end)
{
    bool flag = true;
    for (int i = start; i < end; ++i)
        if (s[i] != s[i + 1])
            flag = false;
    if (flag)
        return 1 + dp(end + 1);
    else
        return INF;
}
 
int case2(int start, int end)
{
    int count = 0;
    for (int i = start; i < end; ++i)
        if (s[i] - s[i + 1] == 1)
            ++count;
    if (count == end - start)
        return 2 + dp(end + 1);
    count = 0;
    for (int i = start; i < end; ++i)
        if (s[i] - s[i + 1] == -1)
            ++count;
    if (count == end - start)
        return 2 + dp(end + 1);
    return INF;
}
 
int case3(int start, int end)
{
    if (end - start == 2)
        if (s[end] == s[start])
            return 4 + dp(end + 1);
        else
            return INF;
 
    if (end - start == 3)
        if (s[start] == s[end - 1] && s[start + 1] == s[end])
            return 4 + dp(end + 1);
        else
            return INF;
 
    if (s[start] == s[end] && s[start] == s[start + 2] && s[start + 1] == s[end - 1])
        return 4 + dp(end + 1);
    return INF;
}
 
int case4(int start, int end)
{
    int gap = s[start + 1] - s[start];
    int count = 0;
    for (int i = start + 1; i < end; ++i)
        if (s[i + 1] - s[i] == gap)
            ++count;
    if (count == end - start - 1)
        return 5 + dp(end + 1);
    return INF;
}
 
int case5(int start, int end)
{
    return dp(end + 1) + 10;
}
 
int dp(int idx)
{
    if (idx == len)
        return 0;
    int &ret = cache[idx];
    if (ret != -1)
        return ret;
    ret = INF;
    for (int i = 2; i <= 4; ++i)
    {
        if (idx + i >= len)
            continue;
        ret = min(ret, case1(idx, idx + i));
        ret = min(ret, case2(idx, idx + i));
        ret = min(ret, case3(idx, idx + i));
        ret = min(ret, case4(idx, idx + i));
        ret = min(ret, case5(idx, idx + i));
    }
    return ret;
}
 
int main()
{
    int C;
    cin >> C;
    for (int tn = 0; tn < C; ++tn)
    {
        init();
        cout << dp(0) << "\n";
    }
}
 
 cs

 

 

 

 

https://algospot.com/judge/problem/read/PI

 

algospot.com :: PI

원주율 외우기 문제 정보 문제 (주의: 이 문제는 TopCoder 의 번역 문제입니다.) 가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다. 이 때, 각 조각들의 난이

algospot.com

 

 

 

 

 

PI

DP문제

cache[i] : i번째부터 시작하는 원주율의 최소난이도를 저장합니다.