https://programmers.co.kr/learn/courses/30/lessons/60060

 

코딩테스트 연습 - 가사 검색 | 프로그래머스

 

programmers.co.kr

 

트라이로 푼 문제

 

find를 비재귀로 했다가 효율성 3번만 계속 틀렸다

 

진짜 미쳐버리는줄 알았다 시간도 더빠르고 메모리도 동일한데 뭐가 문제란 말인지

 

정확성 테스트에서 예외 확인하고 효율성에서 시간 확인하는게 아닌건가??

 

맞왜틀

 

진자로 너무 화가낫다..

 

발상 자체는 금방 했는데 저 3번때문에 며칠을 꼬라박았다

 

답은 재귀였다.

 

아나

 

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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
struct Trie
{
    Trie()
    {
        memset(next, 0, sizeof(next));
        /*for (int i = 0; i < 26; ++i)
        {
            next[i] = nullptr;
        }*/
    }
    ~Trie()
    {
        for (int i = 0; i < 26; ++i)
        {
            if (next[i])
            {
                //std::cout << (char)('a' + i);
                delete next[i];
                //std::cout << '\n';
            }
        }
    }
 
    void insert(const char* word)
    {
        if (*word == '\0')
        {
            return;
        }
        ++size;
 
        int idx = *word - 'a';
        if (next[idx] == nullptr)
        {
            next[idx] = new Trie;
        }
        next[idx]->insert(word + 1);
    }
 
    unsigned int find_how_many(const char* word)
    {
        //엉뚱한 글자가 나오면 0을 리턴합니다
        if (next[word[0] - 'a'] == nullptr)
        {
            return 0;
        }
        // "?????"같은 상황을 대비해 첫글자가 '\0'이라면 해당 글자수의 모든 사이즈를 리턴합니다
        //if (*word == '\0')
        if (*word == '?')
        {
            return size;
        }
        
        //word를 따라가기 위한 idx 변수를 만듭니다.
        unsigned int idx = 0;
        //트라이의 링크를 따라가기 위한 tour변수를 만들었습니다.
        Trie* tour = next[word[idx++] - 'a'];
        //'f????'같은 상황을 대비해 idx를 올리고 검사합니다.
        //if (word[idx] == '\0')
        if (word[idx] == '?')
        {
            return tour->size;
        }
 
        //word와 트라이 링크를 같이 따라갑니다
        while (tour->next[word[idx] - 'a'] != nullptr)
        {
            tour = tour->next[word[idx++] - 'a'];
 
            //if (word[idx] == '\0')
            if (word[idx] == '?')
            {
                //word의 끝이 나오면 사이즈를 리턴합니다
                return tour->size;
            }
        } 
        return 0;
    }
 
    //unsigned int find_how_many(const char* word)
    //{
    //    if (*word == '?')
    //    {
    //        return size;
    //    }
    //    if (next[word[0] - 'a'] == nullptr)
    //    {
    //        return 0;
    //    }
 
    //    return next[word[0] - 'a']->find_how_many(word + 1);
    //}
 
public:
    Trie* next[26];
    unsigned int size = 0;
};
 
Trie trieArr[10001];
Trie rtrieArr[10001];
 
vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer(queries.size());
    //std::unordered_map<int, Trie> trieArr;
    //std::unordered_map<int, Trie> rtrieArr;
    //trieArr.reserve(10010);
    //rtrieArr.reserve(10010);
 
    std::string token;
    for (auto& it : words)
    {
        //입력받은 단어를 정방향으로 한번, 역방향으로 한번 넣었습니다.
        token.clear();
        token = it;
        std::reverse(token.begin(), token.end());
        rtrieArr[it.size()].insert(token.c_str());
        trieArr[it.size()].insert(it.c_str());
    }
 
    int idx = 0;
    for (auto& it : queries)
    {
        //첫글자가 ?이 아니면 정방향, ?이 나올때까지 쿼리의 단어를 token에 넣고 find를 돌렸습니다
        token.clear();
        if (it.front() != '?')
        {
 
            //int i = 0;
            //while (it[i] != '?')
            //{
            //    token += it[i++];
            //}
            //token += '\0';
            
            //answer[idx++] = trieArr[it.size()].find_how_many(token.c_str());
            
            answer[idx++] = trieArr[it.size()].find_how_many(it.c_str());
        }
        else
        {
            //첫글자가 ?이면 역방향, 위와 마찬가지로 ?가 나올때까지 역방향으로 token에 넣고 find 함수에 넣었습니다
            
            std::reverse(it.begin(), it.end());
            //int i = it.size() - 1;
            //while (it[i] != '?')
            //{
            //    token += it[i--];
            //}
            //token += '\0';
 
            //answer[idx++] = rtrieArr[it.size()].find_how_many(token.c_str());
            
            answer[idx++] = rtrieArr[it.size()].find_how_many(it.c_str());
        }
    }
    return answer;
}
 
int main()
{
    std::vector<std::string> words = { "frodo", "front", "frost", "frozen", "frame", "kakao" };
    std::vector<std::string> queries = { "fro??", "????t", "fr???", "fro???", "pro?" };
    for (auto it : solution(words, queries))
    {
        std::cout << it << ' ';
    }
    return 0;
}
 cs

문제의 틀린 답. 주석처리 된 find_how_many 재귀함수를 사용하면 정답이다.

저작자표시

'알고리즘' 카테고리의 다른 글

이분탐색  (0) 2020.03.05
카카오 2020 5번 - 기둥과 보(구현)  (0) 2020.02.16
백준 2658: 직각이등변삼각형찾기(구현)  (0) 2020.02.01
카카오 2020 3번 - 자물쇠와 열쇠(주석미완)  (0) 2020.02.01
백준 2667: 단지번호붙이기 (플러드필, dfs)  (0) 2019.12.15

https://www.acmicpc.net/problem/2658

 

2658번: 직각이등변삼각형찾기

입력된 모양이 직각이등변 삼각형을 이루는 경우에는 세 꼭짓점의 위치를 출력하고, 그렇지 않은 경우에는 0을 출력한다. 각 꼭짓점의 위치를 한 줄에 두 개의 수로 출력한다. 두 수는 하나의 빈 공백을 두고 출력한다. 첫째 수는 그 꼭짓점이 위에서부터 몇 번째 줄에 있는가 나타내며, 두 번째 수는 왼쪽부터 몇 번째 칸에 있는가를 나타내야 한다. 꼭짓점을 출력할때는 첫째 수가 작은 것부터, 첫째 수가 같을 경우 두 번째 수가 작은 것부터 출력한다.

www.acmicpc.net

 

진짜 머리 쥐어뜯으면서 구현함. 카카오 2020 3번보다 어려웠음..

 

알고리즘 오픈챗에서 누군가가 자기는 위치, 크기, 각도별로 모든 삼각형을 다 만들어서 하나씩 비교했을것같다고 말했는데

 

나는 어케 만들어야할지 감도 안오고 해서 일단 하던대로 진행함

 

그리고 성공하자마자 제출하고 추후에 코드정리는 따로 안해서 성공 당시 그대로의 코드임, 굉장히 난잡하고 더러움

 

그래도 해내서 행복함

 

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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
 
struct pos
{
    int x;
    int y;
};
 
char arr[11][11];
char visit[11][11];
int dy[8] = { -1, -1, 0, 1, 1,  1,  0, -1 };
int dx[8] = {  0,  1, 1, 1, 0, -1, -1, -1 };
bool isFilled = true;
std::vector<pos> tri;
 
bool cmp(const pos& first, const pos& second)
{
    if (first.y < second.y)
        return true;
    else if (first.y == second.y)
        return first.x < second.x;
    else
        return false;
}
 
void pp()
{
    std::cout << "-------------------\n";
    for (int y = 0; y <= 10; ++y)
    {
        for (int x = 0; x <= 10; ++x)
        {
            std::cout << visit[y][x];
        }
        std::cout << '\n';
    }
 
}
 
//정점을 찾아서 리턴함
pos FindVertex(int x, int y, int delta)
{
    while (true)
    {
        pos val = { x, y };
        visit[y][x] = '1';
    
        y += dy[delta];
        x += dx[delta];
        if (arr[y][x] == '0' || y < 1 || 10 < y || x < 1 || 10 < x)
        {
            return val;
        }
    }
}
 
void FindTri()
{
    for (int y = 1; y <= 10; ++y)
    {
        for (int x = 1; x <= 10; ++x)
        {
            if (arr[y][x] == '1')
            {
                tri.push_back({ x, y });
                //dy[8], dx[8]의 8방향 확인
                for (int i = 0; i < 8; ++i)
                {
                    //010
                    //111
                    //같은 상황에서 사용
                    if (arr[y + dy[3]][x + dx[3]] == '1' && arr[y + dy[4]][x + dx[4]] == '1' && arr[y + dy[5]][x + dx[5]] == '1' && i == 4) continue;
                    //111
                    //110
                    //100
                    //같은 상황에서 사용
                    if (arr[y + dy[2]][x + dx[2]] == '1' && arr[y + dy[3]][x + dx[3]] == '1' && arr[y + dy[4]][x + dx[4]] == '1' && i == 3) continue;
                    //아무것도 없는 경우
                    if (arr[y + dy[i]][x + dx[i]] == '0') continue;
 
                    pos tmp = FindVertex(x, y, i);
                    if (tmp.x != x || tmp.y != y)
                    {
                        //찾은 정점이 자기 자신이 아닌경우 정점을 벡터에 추가
                        tri.push_back(tmp);
                    }
 
                }
 
                return;
            }
        }
    }
}
 
//찾은 삼각형 말고 다른 삼각형이 있는지 확인함
bool FindOther()
{
//    std::cout << '\n';
    for (int y = 1; y <= 10; ++y)
    {
        for (int x = 1; x <= 10; ++x)
        {
        //    std::cout << visit[y][x];
            if (visit[y][x] == '1')
            {
                continue;
            }
 
            if (arr[y][x] != '0')
            {
                return true;
            }
        }
    //    std::cout << '\n';
    }
    return false;
}
 
//찾은 삼각형의 내부가 1로 채워져 있는지 확인함, 플러드필처럼 동작함
void IsFilled(pos point)
{
    if (visit[point.y][point.x] == '0' && arr[point.y][point.x] == '1')
    {
        visit[point.y][point.x] = '1';
        for (int i = 0; i < 8; i += 2)
        {
            IsFilled({ point.x + dx[i], point.y + dy[i] });
        }
    }
    else if (visit[point.y][point.x] == '1' && arr[point.y][point.x] == '1')
    {
        return;
    }
    else if (visit[point.y][point.x] == '0' && arr[point.y][point.x] == '0')
    {
        isFilled = false;
    }
}
 
//맨 위 정점(a)에서 뻗어나온 두 정점(b, c)까지의 변 ab, ac와 별개로, 변 bc가 제대로 존재하는지 확인함
bool Fooooooo()
{
    //삼각형이 작아서 확인이 불가능한 경우
    //010 || 11 ||
    //111 || 10 || 등등
    //이러한 경우 참(변 bc가 제대로 존재한다)리턴함
    for (int i = 0; i < 8; ++i)
    {
        if (tri[1].x + dx[i] == tri[2].x && tri[1].y + dy[i] == tri[2].y)
        {
            return true;
        }
    }
    //맨 우측 하단 정점에서 좌측 하단 정점까지 값이 존재하는지 검사함
    pos drawline = { tri[1].x, tri[1].y };
    for (int i = 4; i < 8; ++i)
    {
        if (arr[drawline.y + dy[i]][drawline.x + dx[i]] == '1' && visit[drawline.y + dy[i]][drawline.x + dx[i]] == '0')
        {
            while (drawline.x != tri[2].x || drawline.y != tri[2].y)
            {
                drawline.x += dx[i];
                drawline.y += dy[i];
                //pp();
 
                if (arr[drawline.y][drawline.x] != '1')
                {
                    return false;
                }
                visit[drawline.y][drawline.x] = '1';
            }
            return true;
        }
    }
    return false;
}
 
//0001000000
//0011000000
//0111000000
//1111000000
//0000000000
//0000000000
//0000000000
//0000000000
//0000000000
//0000000000
 
//이등변 삼각형이 맞는지 확인하는 사실상의 메인 함수
bool IsRightTri()
{
    FindTri();
 
    //정점이 3개가 아닌경우 거짓
    if (tri.size() != 3)
    {
        return false;
    }
 
    //변 bc가 존재하지 않는경우 거짓
    if (Fooooooo() == false)
    {
        return false;
    }
 
    //이등변삼각형의 중심(삼각형의 중심 공식 사용)으로부터 삼각형의 내부가 다 채워져있는지 확인
    IsFilled({ (tri[0].x + tri[1].x + tri[2].x) / 3, (tri[0].y + tri[1].y + tri[2].y) / 3 });
    //귀찮아서 전역으로 뺌
    if (isFilled == false)
    {
        return false;
    }
 
    //삼각형 외부에 다른 값이 있는지 확인, 있으면 거짓
    if (FindOther())
    {
        return false;
    }
 
    //정점들의 y값부터 정렬
    std::sort(tri.begin(), tri.end(), cmp);
    //일단 급해서 마구잡이로 코드를 짬
    for (int i = 0; i < 2; ++i)
    {
        //하나의 변이 반드시 수직선과 수평선인 이등변삼각형의 경우 정점 3개의 y와 x값중 반드시 중복되는 값이 나타남.
        int vertexs[3];
        if (i == 0)
        {
            vertexs[0] = tri[0].y;
            vertexs[1] = tri[1].y;
            vertexs[2] = tri[2].y;
        }
        else
        {
            vertexs[0] = tri[0].x;
            vertexs[1] = tri[1].x;
            vertexs[2] = tri[2].x;
        }
 
        std::sort(vertexs, vertexs + 3);
 
        //그를 위해 각각의 값을 정렬, 중복값이 나온다면 이등변 삼각형
        if (vertexs[0] == vertexs[1] || vertexs[1] == vertexs[2])
        {
            return true;
        }
    }
 
    return false;
}
//1110000000
//1100000000
//1000000000
//0000000000
//0000000000
//0000000000
//0000000000
//0000000000
//0000000000
//0000000000
int main()
{
    //삼각형부터 제대로 찾아보자
    for (int y = 1; y <= 10; ++y)
    {
        std::string input;
        std::cin >> input;
        for (int x = 1; x <= 10; ++x)
        {
            arr[y][x] = input[x - 1];
            visit[y][x] = '0';
        }
    }
 
    if (IsRightTri() == false)
    {
        std::cout << 0;
        return 0;
    }
    else
    {
        for (int i = 0; i < 3; ++i)
            std::cout << tri[i].y << ' ' << tri[i].x << '\n';
        return 0;
    }
}
 cs

 

저작자표시

'알고리즘' 카테고리의 다른 글

카카오 2020 5번 - 기둥과 보(구현)  (0) 2020.02.16
카카오 2020 4번 - 가사 검색(트라이)  (0) 2020.02.08
카카오 2020 3번 - 자물쇠와 열쇠(주석미완)  (0) 2020.02.01
백준 2667: 단지번호붙이기 (플러드필, dfs)  (0) 2019.12.15
플로이드 워샬(미완)  (0) 2019.12.15

https://www.acmicpc.net/problem/11066


거의 일주일동안 푼 문제, 답을 봐도 뭔소린지 모르겠어서 멘탈이 터졌다.


문제

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.


예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이때 필요한 총 비용은 70+80+150=300 이다.


소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.


입력

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 500)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.


출력

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.


예제 입력 1 

2

4

40 30 30 50

15

1 21 3 4 5 35 5 4 3 5 98 21 14 17 32

예제 출력 1 

300

864


코드는 다음과 같다.

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
#include <iostream>
 
#define min(a,b)            (((a) < (b)) ? (a) : (b))
 
long long dp[501][501];
long long sum[501];
int T, K;
 
int main()
{
    std::cin >> T;
    for (int testCase = 0; testCase < T; ++testCase)
    {
        std::cin >> K;
        for (int i = 1; i <= K; ++i)
        {
            std::cin >> sum[i];
            sum[i] += sum[i - 1];
        }
        for (int x = 2; x <= K; ++x)
            for (int y = 1; y + x - 1 <= K; ++y)
            {
                dp[y][x + y - 1] = 2147483647;
                for (int m = y + 1; m - y < x; ++m)
                    dp[y][x + y - 1] = min(dp[y][x + y - 1], dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]);
            }
        std::cout << dp[1][K] << '\n';
 
 
        for (int y = 0; y <= K + 2; ++y)
        {
            for (int x = 0; x <= K + 2; ++x)
            {
                std::cout.width(3);
                std::cout << dp[y][x] << ' ';
            }
            std::cout << '\n';
        }
    }
    return 0;
}
cs


예제 1의 설명으로는 좀 애매한 부분이 있어서.. 예제 2의 동작원리를 보게 되었다.



행렬은 이러한 숫자들로 구성이 되어 있는데,


3중 반복문이 어떻게 동작하는지 살펴봐야 한다.


1
2
3
4
5
6
7
for (int x = 2; x <= K; ++x)
    for (int y = 1; y + x - 1 <= K; ++y)
    {
        dp[y][x + y - 1] = 2147483647;
        for (int m = y + 1; m - y < x; ++m)
            dp[y][x + y - 1] = min(dp[y][x + y - 1], dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]);
    }
cs



행렬은 x좌표가 2에서 시작한다. y는 x좌표의 값을 더해(-1도 추가) 입력받은 K장까지 증가하게 된다. int y = 1; y + x - 1 <= K; ++y


 y는 1부터 15까지 모든 행을 다 순회하기 때문에 1에서 시작한다. y + x - 1 <= K인 이유는 y <= K일 경우에 행렬 오버플로가 발생하기 때문


m은 양옆의 원소들을 비교하기 위해 존재하는 반복문이다. 자세한 동작은 계속 설명하면서 다시 보자.


첫번째 반복의 상황에선 x = 2, y = 1일 때, m = y + 1이 2, 즉 1 < 2(m - y < x) 이기 때문에 x = 2, y = 1, m = y + 1 일 때



dp[y][x + y - 1]이 2147483647(INT_MAX)이고,


min(dp[y][x + y - 1], dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1])

 =

dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]

dp[2][2] + dp[1][1] + sum[2] - sum[0]

0              +    0        +  22(sum[2])   -  0(sum[0])

이기 때문에 22가 들어가게 되는 것이다.


y가 2일 때는 25(sum[x + y - 1] = sum[3]) - 1(sum[y - 1] = sum[1]) 이다.


즉,

dp[3][3] + dp[2][2] + sum[3] - sum[1] = 24이다.


아직까진 반복문 m이 한번밖에 돌지 않는다. 또한 동작도 납득할 수 있는 수준이다.



이제 x = 3 일 때, y가 어떻게 동작하는지 알아야 한다.


for (int m = y + 1; m - y < x; ++m)이다. 즉 m = 2일때, m - y < x(2 - 1 < 2), 반복문은 두번 반복된다.


m = 2 일 때,

y = 1이고, 식에 의해 25(sum[3]) - 0(sum[0]) = 25이다. dp[m][x + y - 1] + dp[y][m - 1]는 dp[2][3] + dp[1][2](0 + 24) 이다.


dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]

즉, 24 + 25 = 49 이다. dp[y][x + y - 1]는 49이다.


m = 3 일 때,

y = 1이고, 식에 의해 25(sum[3]) - 0(sum[0]) = 25이다. dp[m][x + y - 1] + dp[y][m - 1]는 dp[3][3] + dp[1][1](22 + 0) 이다.


dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]

즉, 22 + 25 = 47 이다. 49 > 47 이기 때문에 dp[y][x + y - 1]는 47이다.



혼란스러운 머리를 부여잡고 여기까지 따라왔다면 이것 또한 이해할수있따


dp[1][4]는 (22 + 7) + (1 + 21 + 3 + 4) = 58 이고, 

dp[2][5]는 (19 + 0) + (21 + 3 + 4 + 5) = 52 이다.


사진상의 행렬 비교 순서는 m = 2 일 때,

(35 + 0) + (1 + 21 + 3 + 4)

(7 + 22) + (1 + 21 + 3 + 4)

(0 + 47) + (1 + 21 + 3 + 4)


이 중 가장 작은것은 58이기 때문에, dp[1][4]는 58이 들어가는 것



같은 원리다. 계산은 이와 같은 로직으로 돌아가게 된다.


어째서 이러한 동작을 하게 되냐면,


잘 모르겠다ㅎ 대충 이분해서 최솟값을 계산하는 것은 얼추 알 것 같다. 설명할 자신은 없지만



첫 번째 사진은 1, 21 ~ 32 중 최소 비용을 쓴 크기 (839 + 0) + sum[15]

두 번째 사진은 1 ~ 21, 3 ~ 32 중 최소 비용을 쓴 크기 (739 + 22) + sum[15]

...

n  번째 사진은 1 ~ 35, 5 ~ 32 중 최소 비용을 쓴 크기 (515 + 144) + sum[15]

515 : 1 ~ 35 중 최소 비용

144 : 5 ~ 32 중 최소 비용

... K번까지 돌아가는 것이다.


그냥 그러려니 하고 암기하자...

저작자표시

'알고리즘' 카테고리의 다른 글

2. C++언어 역사 개요..?  (0) 2019.10.07
1. 희망의 나라로 알고리즘  (0) 2019.10.07
백준 1912: 연속합(DP)  (0) 2019.08.27
백준 9251: LCS(DP)  (0) 2019.08.26
백준 2565: 전깃줄(DP)  (0) 2019.08.23

https://www.acmicpc.net/problem/1912



 

 시간 제한

 2 초 

 메모리 제한

 128 MB

 제출

 51339

 정답

 14220

 맞은 사람

 9806

 정답 비율 

 27.120%


문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.


예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.


입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.


기존 코드


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
#include <iostream>
#include <algorithm>
 
int dp[100010];
int arr[100010];
 
int max(int first, int second) 
{ 
    return first > second ? first : second;
}
 
int main()
{
    int n = 0;
    std::cin >> n;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> arr[i];
        dp[i] = -1001;
    }
    dp[0] = arr[0];
    for (int i = 1; i < n; ++i)
    {
        dp[i] = max(arr[i], arr[i] + dp[i - 1]);
    }
    std::sort(dp, dp + n);
    std::cout << dp[n - 1];
    return 0;
}
cs

시간 20ms


바꾼 코드


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
#include <iostream>
#include <algorithm>
 
int dp[100010];
int arr[100010];
 
int max(int first, int second) { return first > second ? first : second; }
 
int main()
{
    std::cin.tie(0);
    std::cin.sync_with_stdio(false);
    std::cout.tie(0);
    std::cout.sync_with_stdio(false);
    int n = 0;
    std::cin >> n;
    dp[0] = -1001;
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> arr[i];
        dp[i] = -1001;
        dp[i] = max(arr[i], arr[i] + dp[i - 1]);
    }
    std::sort(dp, dp + n + 1);
    std::cout << dp[n];
    return 0;
}
cs

시간 8ms


어이어이 너무 쉬운거 아니냐고 wwwwwww


LIS LCS에서 뚝배기터지고 나온 문제라 와 시발 얼마나 어려울까 해쓴ㄴ데


문제가 생각보다 너무 쉬울것같아서 아.. 뭔가 어려운게 있겠지? 있겠지? 해서

(코드 짠시간보다 이게 될까 안될까 고민하는 시간이 더 길었다)


부들부들 떨면서 제출했는데 그냥 통과대버렷다


쉬운문제는 맞는것같은데 왤캐 정답률이 낮지


히히ㅣㅎ킿킿ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ

저작자표시

'알고리즘' 카테고리의 다른 글

1. 희망의 나라로 알고리즘  (0) 2019.10.07
백준 11066: 파일 합치기(DP)  (0) 2019.09.06
백준 9251: LCS(DP)  (0) 2019.08.26
백준 2565: 전깃줄(DP)  (0) 2019.08.23
백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23

https://www.acmicpc.net/board/view/28163


5시간동안 개삽질하고


답 5분 보고 어이없어서


멘탈터짐


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
unsigned int max(unsigned int first, unsigned int second)
{
    return first > second ? first : second;
}
 
unsigned int dp[1001][1001];
 
int main()
{
    std::string A, B;
    std::cin >> A >> B;
    for (int y = 1; y <= A.size(); ++y)
    {
        for (int x = 1; x <= B.size(); ++x)
        {
            if (A[y - 1] == B[x - 1])
                dp[y][x] += dp[y - 1][x - 1] + 1;
            else
                dp[y][x] = max(dp[y][x - 1], dp[y - 1][x]);
        }
    }
    for (int y = 0; y <= A.size(); ++y)
    {
        for (int x = 0; x <= B.size(); ++x)
        {
            std::cout << dp[y][x]; //dp[A.size()][B.size()]가 정답
        }
        std::cout << '\n';
    }
    return 0;
}
 
cs


2차원배열을 이용하는 것도 참


생각도 못했다


걍 너무 내가 병신쪼다같고 막.. 그래....


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
unsigned int getlen(int it, unsigned int n)
{
    //KJFSDFLKDF
    int tmp = 1;
    int pos = n;
    for (unsigned int i = it; i < str1.size(); ++i)
    {
        //findPos = prePos;
        //KJSDFKSDFLKDFJS SKDJKFLSKDJFLKSDJF
        auto finder = str2.find(str1[i], pos);
        if (finder == std::string::npos) continue;
        if (dp2[finder] != 0 && dp2[finder] <= tmp) { ++pos; --i;  continue; }
        unsigned int j = finder;
        while (j < str2.size())
        {
            if (dp2[j] != 0) break;
            ++j;
            //if (tmp > dp2[j] && str2[j] == str1[i]) break;
        }
        if (tmp > dp2[j] && dp2[finder] != 0) { ++pos; --i;  continue; }
        if (j == str2.size())
        {
            dp2[finder] = ++tmp;
        }
        else
        {
            if (str1[i] == str2[j] && tmp < dp2[j]) continue;
            dp2[finder] = dp2[j];
            tmp = dp2[j];
            dp2[j] = 0;
        }
        //prePos = finder;
        //int jtmp = 0;
        //for (unsigned int j = i + 1; j < str1.size(); ++j)
        //{
        //    findPos = finder;
        //    finder = str2.find(str1[j], findPos);
        //    if(finder == std::string::npos) continue;
        //    ++jtmp;
        //    if (finder == str2.size() - 1) break;
        //}
        //cnt = cnt > tmp + jtmp ? cnt : tmp + jtmp;
    }
    std::cout << '\n';
    cnt = cnt > tmp ? cnt : tmp;
    for (int i = 0; i < str2.size(); ++i)
        std::cout << dp2[i] << ' ';
    return cnt;
}
 
int main()
{
    std::cin >> str1 >> str2;
    int dcnt = 0;
    for (unsigned int i = 0; i < str1.size(); ++i)
    {
        cnt = 0;
        auto startPoint = str2.find(str1[i]);
        if(startPoint == std::string::npos) continue;
        std::cout << str2[startPoint] << ' ';
        dp1[dcnt++] = getlen(i + 1, startPoint + 1);
    }
    std::sort(dp1, dp1 + str1.size());
    std::cout << dp1[str1.size() - 1];
    return 0;
}
cs


똥꼬쑈의 흔적


결국 대패배


저작자표시

'알고리즘' 카테고리의 다른 글

백준 11066: 파일 합치기(DP)  (0) 2019.09.06
백준 1912: 연속합(DP)  (0) 2019.08.27
백준 2565: 전깃줄(DP)  (0) 2019.08.23
백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22

+ Recent posts

티스토리툴바