repl.it
C++

No description

fork
loading
Files
  • main.cpp
main.cpp
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/*
문제 (PI)

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

이 때, 각 조각들의 난이도는 다음과 같이 정해집니다:

모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1
숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2
두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4
숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5
그 외의 경우 난이도: 10

원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 3자리에서 5자리까지 끊어 읽고 싶습니다. 
최소의 난이도를 계산하는 프로그램을 작성하세요.

예제 입력
12341234 
11111222 
12122222 
22222222 
12673939 

예제 출력
4
2
5
2
14
*/

#include <iostream>
#include <climits>
#include <vector>

template <template <class...> class TT, class ...T>
std::ostream& operator<<(std::ostream& os, const TT<T...>& c)
{
    os << "{ ";
    for (const auto& x : c)
        os << x << " ";
    os << "}";
    return os;
}

size_t calculatePoint(const std::vector<int>& input, int start, int end) {
    if (end - start) < 2 return 99999;
    bool isAllSame = true;
    for (int i = start; i < end; i++) {
        if (input[i] != input[i+1]) {
            isAllSame = false;
            break;
        }
    }
    if (isAllSame) return 1;

    bool isOneIncrease = true;
    for (int i = start; i < end; i++) {
        if (input[i] + 1 != input[i+1]) {
            isOneIncrease = false;
            break;
        }
    }
    if (isOneIncrease) return 2;

    bool isOneDecrease = true;
    for (int i = start; i < end; i++) {
        if (input[i] - 1 != input[i+1]) {
            isOneDecrease = false;
            break;
        }
    }
    if (isOneDecrease) return 2;

    bool isTwoAlternating = true;
    int temp1 = -1;
    int temp2 = -1;
    if (start%2 == 0) {
        temp1 = input[start+1];
        temp2 = input[start];
    } else {
        temp1 = input[start];
        temp2 = input[start+1];
    }
    
    for (int i = start+2; i < end; i++) {
        if (i%2 == 0) {
            if (input[i] != temp2) {
                isTwoAlternating = false;
                break;
            }
        }
        else {
            if (input[i] != temp1) {
                isTwoAlternating = false;
                break;
            }
        }
    }
    if (isTwoAlternating) return 4;

    bool isProgressiveSequence = true;
    int diff = input[start+1] - input[start];
    for (int i = start+1; i < end; i++) {
        if (input[i+1] - input[i] != diff) {
            isProgressiveSequence = false;
            break;
        }
    }
    if (isProgressiveSequence) return 5;

    return 10;
}

size_t classify(const std::vector<int>& input)
{
    size_t size = input.size();
    std::vector<int> memo(size);
    
    for (int i = 0; i < size; i++) {
        int end = i;
        int start = 
    }

    return memo[size-1];
}

int main()
{
    std::vector<int> test1({1,2,3,4,1,2,3,4});
    std::vector<int> test2({1,1,1,1,1,2,2,2});
    std::vector<int> test3({1,2,1,2,2,2,2,2});
    std::vector<int> test4({2,2,2,2,2,2,2,2});
    std::vector<int> test5({1,2,6,7,3,9,3,9});
    
    std::cout << classify(test1) << std::endl;
    std::cout << classify(test2) << std::endl;
    std::cout << classify(test3) << std::endl;
    std::cout << classify(test4) << std::endl;
    std::cout << classify(test5) << std::endl;
}
Fetching token
?