기술 블로그

2382번 미생물 격리 본문

알고리즘 문제/SW Expert Academy

2382번 미생물 격리

parkit 2018. 8. 29. 14:20
728x90
반응형

재미있는 문제였다.


생각했던 것보다 조건이 1 ~ 2개 정도 더 많아서, 생각을 좀 요구하는 문제였다.


난이도는 어렵지는 않았다.


하여튼 문제는 다 풀었다고 생각하여서, 제출을 해봤는데 오류가 발생한 것이다.


분명, 내 Visual Studio 2017에서는 오류 발생없이, 

sample_input.txt에 있는 예제 10개 모두 잘 실행되었고, 답도 맞았다.


이유를 보아하니 vector인 v에 push_back을 할 때,  

각 변수에 대한 타입 매칭(?)이 안 맞는 것 같은데, 분명 타입도 다 맞게 설정하였는데도 그렇다.


그래서, 어쩔 수 없이 vector v를 배열 형태로 선언하여, resize해주고 난 후에 풀었더니 PASS가 떴다.




이 문제에서 기억해야할 것(PASS 뜬 코드 기준)

1. 조건을 잘 생각해봐야한다.

2. 131 ~ 138번 째 코드에서 v[update[s]]라고 해야하는데, 생각없이 v[s]라고 하였었다.

3. 100, 112번 째 줄 코드에서 군집이 살아 있을 때도 생각해줘야하는데, 단순 '사용 여부'만 생각했었다.




https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl&




<SW Expert Academy에 제출하였을 때, 발생한 오류>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
제출 오류
컴파일 오류 : 
오류 메세지 : 
solution.cpp: In function ‘int main()’:
solution.cpp:162:40: error: no matching function for call to ‘std::vector<microorganism>::push_back(<brace-enclosed initializer list>)’
    v.push_back({ R, C, Cnt, Dir, true });
                                        ^
solution.cpp:162:40: note: candidates are:
In file included from /usr/include/c++/4.8.2/vector:64:0,
                 from /usr/include/c++/4.8.2/queue:61,
solution.cpp:2:
/usr/include/c++/4.8.2/bits/stl_vector.h:901:7: note: void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = microorganism; _Alloc = std::allocator<microorganism>; std::vector<_Tp, _Alloc>::value_type = microorganism]
       push_back(const value_type& __x)
       ^
/usr/include/c++/4.8.2/bits/stl_vector.h:901:7: note:   no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘const value_type& {aka const microorganism&}’
/usr/include/c++/4.8.2/bits/stl_vector.h:919:7: note: void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = microorganism; _Alloc = std::allocator<microorganism>; std::vector<_Tp, _Alloc>::value_type = microorganism]
       push_back(value_type&& __x)
       ^
/usr/include/c++/4.8.2/bits/stl_vector.h:919:7: note:   no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘std::vector<microorganism>::value_type&& {aka microorganism&&}’
cs







<SW Expert Academy에 제출하였을 때, 오류가 발생한 코드(VS에서는 정상 작동)>

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
#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
typedef struct microorganism // 미생물
{
    int r = 0; // 세로 위치
    int c = 0; // 가로 위치
    int micro_count = 0; // 미생물 수
    int direction = 0; // 이동 방향, 상: 1, 하: 2, 좌: 3, 우: 4
    bool live = true; // 살아있는지 여부
}microorganism;
 
int N = 0, M = 0, K = 0;
 
int map[101][101] = { 0, };
 
vector<microorganism> v;
 
void move()
{
    for (int i = 0; i < K; i++)
    {
        if (v[i].live) // 미생물이 살아있다면
        {
            if (v[i].direction == 1) // 상
            {
                --v[i].r;
 
                if (v[i].r == 0 || v[i].r == N - 1 || v[i].c == 0 || v[i].c == N - 1) // 약품 구역이라면
                {
                    v[i].micro_count /= 2; v[i].direction = 2;
 
                    if (v[i].micro_count == 0)
                    {
                        v[i].live = false;
                    }
                }
            }
            else if (v[i].direction == 2) // 하
            {
                ++v[i].r;
 
                if (v[i].r == 0 || v[i].r == N - 1 || v[i].c == 0 || v[i].c == N - 1) // 약품 구역이라면
                {
                    v[i].micro_count /= 2; v[i].direction = 1;
 
                    if (v[i].micro_count == 0)
                    {
                        v[i].live = false;
                    }
                }
            }
            else if (v[i].direction == 3) // 좌
            {
                --v[i].c;
 
                if (v[i].r == 0 || v[i].r == N - 1 || v[i].c == 0 || v[i].c == N - 1) // 약품 구역이라면
                {
                    v[i].micro_count /= 2; v[i].direction = 4;
 
                    if (v[i].micro_count == 0)
                    {
                        v[i].live = false; 
                    }
                }
            }
            else if (v[i].direction == 4) // 우
            {
                ++v[i].c;
 
                if (v[i].r == 0 || v[i].r == N - 1 || v[i].c == 0 || v[i].c == N - 1) // 약품 구역이라면
                {
                    v[i].micro_count /= 2; v[i].direction = 3;
 
                    if (v[i].micro_count == 0)
                    {
                        v[i].live = false;
                    }
                }
            }
        }
    }
    
    vector<int> update;
 
    bool used[1000 + 1] = { false, };
 
    memset(used, false, sizeof(used));
 
    for (int i = 0; i < K; i++)
    {
        if (used[i] || !v[i].live) continue; // 사용되었거나 죽었다면 무시
        
        int max_count = 0, max_index = 0;
 
        update.push_back(i);
        max_count = v[i].micro_count;
        max_index = i;
 
        for (int j = 0; j < K; j++)
        {
            if (i != j)
            {
                if (v[j].live && v[i].r == v[j].r && v[i].c == v[j].c)
                {
                    update.push_back(j);
 
                    if (max_count < v[j].micro_count)
                    {
                        max_count = v[j].micro_count;
                        max_index = j;
                    }
                }
            }
        }
 
        int update_size = update.size();
 
        if (update_size > 1)
        {
            for (int s = 0; s < update_size; s++)
            {
                if (update[s] != max_index)
                {
                    v[update[s]].live = false;
 
                    v[max_index].micro_count += v[update[s]].micro_count;
                }
 
                used[update[s]] = true; // 사용 표시
            }
        }
 
        if (!update.empty()) update.clear();
    }
}
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    for (int tc = 1; tc <= T; tc++)
    {
        int R = 0, C = 0, Cnt = 0, Dir = 0, result = 0;
 
        scanf("%d %d %d", &N, &M, &K);
 
        for(int i=0; i<K; i++)
        {
            scanf("%d %d %d %d", &R, &C, &Cnt, &Dir);
 
            v.push_back({ R, C, Cnt, Dir, true });
        }
 
        while (M--)
        {
            move();
        }
 
        for (int i = 0; i < K; i++)
        {
            if (v[i].live)
            {
                result += v[i].micro_count;
            }
        }
 
        v.clear();
 
        printf("#%d %d\n", tc, result);
    }
    
    return 0;
}
cs







<PASS 뜬 코드, 추가 및 수정 부분은 표시하였음>

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
#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
typedef struct microorganism // 미생물
{
    int r = 0; // 세로 위치
    int c = 0; // 가로 위치
    int micro_count = 0; // 미생물 수
    int direction = 0; // 이동 방향, 상: 1, 하: 2, 좌: 3, 우: 4
    bool live = true; // 살아있는지 여부
}microorganism;
 
int N = 0, M = 0, K = 0;
 
int map[101][101] = { 0, };
 
vector<microorganism> v;
 
void move()
{
    for (int i = 0; i < K; i++)
    {
        if (v[i].live) // 미생물이 살아있다면
        {
            if (v[i].direction == 1) // 상
            {
                --v[i].r;
 
                if (v[i].r == 0 || v[i].r == N - 1 || v[i].c == 0 || v[i].c == N - 1) // 약품 구역이라면
                {
                    v[i].micro_count /= 2; v[i].direction = 2;
 
                    if (v[i].micro_count == 0)
                    {
                        v[i].live = false;
                    }
                }
            }
            else if (v[i].direction == 2) // 하
            {
                ++v[i].r;
 
                if (v[i].r == 0 || v[i].r == N - 1 || v[i].c == 0 || v[i].c == N - 1) // 약품 구역이라면
                {
                    v[i].micro_count /= 2; v[i].direction = 1;
 
                    if (v[i].micro_count == 0)
                    {
                        v[i].live = false;
                    }
                }
            }
            else if (v[i].direction == 3) // 좌
            {
                --v[i].c;
 
                if (v[i].r == 0 || v[i].r == N - 1 || v[i].c == 0 || v[i].c == N - 1) // 약품 구역이라면
                {
                    v[i].micro_count /= 2; v[i].direction = 4;
 
                    if (v[i].micro_count == 0)
                    {
                        v[i].live = false;
                    }
                }
            }
            else if (v[i].direction == 4) // 우
            {
                ++v[i].c;
 
                if (v[i].r == 0 || v[i].r == N - 1 || v[i].c == 0 || v[i].c == N - 1) // 약품 구역이라면
                {
                    v[i].micro_count /= 2; v[i].direction = 3;
 
                    if (v[i].micro_count == 0)
                    {
                        v[i].live = false;
                    }
                }
            }
        }
    }
 
    vector<int> update;
 
    bool used[1000 + 1] = { false, };
 
    memset(used, false, sizeof(used));
 
    for (int i = 0; i < K; i++)
    {
        if (used[i] || !v[i].live) continue; // 사용되었거나 죽었다면 무시
 
        int max_count = 0, max_index = 0;
 
        update.push_back(i);
        max_count = v[i].micro_count;
        max_index = i;
 
        for (int j = 0; j < K; j++)
        {
            if (i != j)
            {
                if (v[j].live && v[i].r == v[j].r && v[i].c == v[j].c)
                {
                    update.push_back(j);
 
                    if (max_count < v[j].micro_count)
                    {
                        max_count = v[j].micro_count;
                        max_index = j;
                    }
                }
            }
        }
 
        int update_size = update.size();
 
        if (update_size > 1)
        {
            for (int s = 0; s < update_size; s++)
            {
                if (update[s] != max_index)
                {
                    v[update[s]].live = false;
 
                    v[max_index].micro_count += v[update[s]].micro_count;
                }
 
                used[update[s]] = true; // 사용 표시
            }
        }
 
        if (!update.empty()) update.clear();
    }
}
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    for (int tc = 1; tc <= T; tc++)
    {
        int R = 0, C = 0, Cnt = 0, Dir = 0, result = 0;
 
        scanf("%d %d %d", &N, &M, &K);
 
        // 추가한 부분
        v.resize(K);
 
        for (int i = 0; i<K; i++)
        {
            scanf("%d %d %d %d", &R, &C, &Cnt, &Dir);
            
            // 수정한 부분
            v[i].r = R;
            v[i].c = C;
            v[i].micro_count = Cnt;
            v[i].direction = Dir;
            v[i].live = true;
        }
 
        while (M--)
        {
            move();
        }
 
        for (int i = 0; i < K; i++)
        {
            if (v[i].live)
            {
                result += v[i].micro_count;
            }
        }
 
        v.clear();
 
        printf("#%d %d\n", tc, result);
    }
 
    return 0;
}
cs







<sample input>

10

7 2 9

1 1 7 1

2 1 7 1

5 1 5 4

3 2 8 4

4 3 14 1

3 4 3 3

1 5 8 2

3 5 100 1

5 5 1 1

10 17 46

7 5 724 2

7 7 464 3

2 2 827 2

2 4 942 4

4 5 604 4

7 2 382 1

6 5 895 3

8 7 538 4

6 1 299 4

4 7 811 4

3 6 664 2

6 8 868 2

7 6 859 2

4 6 778 2

5 4 842 3

1 3 942 1

1 1 805 3

3 2 350 3

2 5 623 2

5 3 840 1

7 1 308 4

1 8 323 3

2 3 82 3

2 6 115 2

8 3 930 1

6 2 72 1

2 1 290 3

4 8 574 4

8 5 150 3

8 2 287 2

2 8 909 2

2 7 588 2

7 3 30 3

5 8 655 3

3 8 537 1

4 2 350 3

5 6 199 1

5 5 734 2

3 3 788 1

8 4 893 1

1 4 421 4

6 3 616 2

1 2 556 4

7 8 8 1

5 2 702 2

4 4 503 3

10 5 28

3 3 796 1

7 2 798 2

2 6 622 1

3 5 179 3

7 8 888 4

5 8 634 3

1 8 646 1

3 7 433 4

6 7 416 1

2 7 651 3

6 4 476 2

5 6 712 4

1 7 869 4

6 1 789 2

8 8 585 3

7 6 426 1

1 5 154 2

1 2 692 1

2 4 549 3

2 1 60 2

4 8 996 4

8 2 437 2

3 6 195 2

1 3 734 4

3 8 355 2

1 1 945 1

2 5 558 2

7 7 144 2

10 22 26

2 2 450 4

6 3 659 1

5 8 24 2

3 7 649 2

3 2 22 3

1 3 905 4

7 8 625 3

6 7 824 3

7 3 159 1

2 7 297 4

7 2 270 2

4 5 985 1

7 1 627 2

3 4 625 4

8 5 972 4

6 6 432 4

6 8 142 1

7 7 900 1

4 1 974 2

4 2 760 4

1 4 550 2

5 7 624 4

4 6 694 1

4 3 593 3

3 1 152 4

1 8 926 1

10 7 15

3 4 227 1

4 7 109 1

3 7 487 2

2 3 627 2

6 1 520 4

7 3 596 4

2 6 525 4

1 5 116 3

7 7 771 4

4 4 520 2

7 5 763 1

5 4 829 3

5 2 578 3

6 8 200 2

3 8 760 4

10 24 12

6 5 887 2

2 3 428 1

2 1 540 2

8 1 356 4

1 7 485 4

5 1 357 3

7 6 271 2

6 2 22 1

6 1 41 2

8 2 565 2

8 5 855 1

6 3 734 1

10 22 44

2 2 963 1

8 4 635 4

4 1 938 4

8 7 511 3

6 8 825 4

6 7 934 3

3 7 701 4

2 7 534 2

5 2 705 1

3 5 300 2

6 2 855 4

7 7 877 4

1 7 443 1

1 2 313 1

3 3 932 2

1 8 831 2

1 1 90 2

2 6 145 3

2 3 740 4

5 3 759 4

1 6 181 1

8 6 608 4

5 6 556 2

2 4 541 4

2 1 174 2

6 1 601 1

7 5 84 4

4 3 970 3

8 8 503 1

3 4 171 3

5 7 913 4

8 1 232 3

7 6 539 4

3 8 648 1

8 2 944 2

2 5 508 2

5 1 87 1

5 8 88 4

2 8 681 2

1 5 758 2

3 1 690 3

6 4 620 3

5 4 783 1

6 6 748 1

10 9 38

2 7 955 1

7 7 25 4

4 2 496 2

1 4 342 1

7 5 72 1

3 7 429 2

5 2 812 3

8 6 36 2

1 6 994 3

1 5 838 1

3 4 131 4

7 2 11 2

6 3 650 3

7 3 353 2

1 7 454 2

8 3 256 4

5 5 213 2

6 5 80 1

2 1 676 4

4 6 561 3

2 5 653 3

3 5 923 3

8 2 259 3

4 4 781 2

1 1 313 2

3 6 938 3

2 6 700 3

4 1 215 2

4 8 39 3

5 1 954 3

6 7 774 1

5 8 541 4

3 1 885 4

7 8 867 2

2 8 825 1

5 6 598 3

6 6 80 3

8 1 405 2

10 16 11

5 7 87 3

2 5 686 1

6 7 64 2

6 8 873 3

5 6 762 2

8 4 268 3

7 3 307 4

1 7 809 3

5 5 293 3

5 1 345 3

4 1 114 4

10 8 19

3 1 52 4

6 8 423 3

7 3 498 4

7 5 633 3

7 7 392 3

6 6 458 4

3 8 830 3

5 1 799 3

1 1 540 3

4 8 567 3

1 6 897 3

5 4 230 1

2 6 229 3

1 5 147 1

4 1 754 2

3 3 569 1

7 8 515 4

2 4 528 4

2 1 962 2

10 24 36

6 6 923 3

7 6 910 2

2 1 278 2

2 5 164 3

8 6 505 4

2 8 970 1

1 1 85 2

1 6 194 1

5 3 572 1

7 4 611 4

6 2 565 4

1 3 609 4

1 7 74 2

6 5 573 4

5 1 31 3

7 7 779 3

7 1 391 3

8 5 364 3

7 8 474 1

5 6 547 3

2 6 195 2

3 7 754 4

1 8 912 1

3 8 415 1

5 8 434 4

5 7 958 4

2 7 700 3

4 5 974 1

4 7 376 4

3 1 111 1

3 6 486 1

8 4 545 1

5 2 237 3

4 2 850 2

2 4 793 2

6 3 877 2

20 5 30

1 14 823 3

6 14 595 4

10 6 1310 3

13 7 1487 3

15 3 258 4

14 15 1286 4

7 7 1128 1

3 10 1503 3

18 8 1881 3

6 17 598 3

1 16 756 4

18 11 1435 2

12 18 1386 3

4 9 48 3

1 9 1840 2

17 8 1599 3

12 5 1328 3

13 12 1794 1

3 1 1432 4

14 9 1497 1

6 2 841 4

10 9 648 1

2 16 633 3

12 3 1990 3

12 6 578 1

8 1 1487 1

6 13 193 1

11 10 1834 1

5 16 529 2

5 14 1392 4


<sample output>

#1 145

#2 5507

#3 9709

#4 2669

#5 3684

#6 774

#7 4797

#8 8786

#9 1374

#10 5040

728x90
반응형
저작자표시

'알고리즘 문제 > SW Expert Academy' 카테고리의 다른 글

2117번 홈 방범 서비스  (0) 2018.09.01
2105번 디저트 카페  (0) 2018.08.31
1952번 수영장  (0) 2018.08.27
1953번 탈주범 검거  (0) 2018.08.25
2383번 점심 식사시간  (0) 2018.08.25
'알고리즘 문제/SW Expert Academy' Related Articles more