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

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

나는 그냥 문제에 나와있는대로 하나하나 처리를 해줬는데 다른 사람들의 풀이를 보니까 더 간단하게 풀었던데 나중에 보고 다시 공부해봐야겠다.

 

먼저 가로방향과 세로방향을 각각 구해줬다.

가로 방향을 구할 때는 모든 행에 대해서 각각의 열을 비교하였다.

  1. j열과 j+1 의 높이가 같다면 다음 열의 비교로 넘어간다.
  2. 높이 차이가 1보다 크다면 경사로를 놓을 수도 없으므로 해당 행에는 활주로 건설이 불가능하다.
  3. 높이차이가 1이라면 경사로를 놓을 수 있는지 확인한다. 밑의 조건에 맞지 않는다면 flag를 false로 바꿔준다.
    1. 경사로의 길이 x만큼을 놓았을 때 범위를 넘어가지 않는지 확인.
    2. 경사로를 놓아줄 x만큼의 칸의 높이가 같은지 확인.
    3. 경사로를 놓을 자리에 이미 경사로가 놓여있지 않은지 확인.
  4. 위의 조건을 모두 통과하였다면 경사로를 놓아줄 것인데 j가 j+1보다 컸다면 j+1부터 뒷쪽으로 경사로를 놓아주면 되고, 반대의 경우에는 j부터 앞쪽으로 경사로를 놓아주면 된다.
  5.  
  6. 행의 열 끝까지가는 동안 flag가 true라면 (위의 조건에서 한번도 걸리지 않았다면) 해당 행은 활주로를 건설할 수 있다.

위와 같은 방식으로 세로 방향도 행과 열을 바꿔서 구해주면된다. 

 

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
#include <iostream>
#include <cstring>
using namespace std;
 
int n, x, ans;
int map[20][20];
bool checkG[20][20];
bool checkS[20][20];
 
int checkGaro() {
    int cnt = 0;
 
    //모든 행을 검사
    for (int i = 0; i < n; i++) {
 
        bool flag = true;
        for (int j = 0; j < n - 1; j++) {
            //높이가 같으면 다음 칸으로 넘어간다
            if (map[i][j] == map[i][j + 1]) continue;
 
 
            //높이 차이를 구해준다.
            int tmp = map[i][j] - map[i][j + 1];
            if (tmp < 0) tmp = -tmp;
 
            //1보다 차이가 크면 경사로를 놓을 수 없으므로 해당 행은 활주로 건설 불가
            if (tmp > 1) {
                flag = false;
                break;
            }
 
 
            //앞쪽이 더 높은 경우 뒷쪽에 경사로 놔준다.
            if (map[i][j] > map[i][j + 1]) {
                //범위를 벗어나는 경우
                if (j + x >= n) {
                    flag = false;
                    break;
                }
 
                //경사로를 x만큼 놓을 수 있는지 검사
                for (int k = j + 1; k < j + x; k++) {
                    //경사로를 놓을 자리의 높이가 같은지 검사
                    if (map[i][k] != map[i][k + 1]) {
                        flag = false;
                        break;
                    }
 
                }
 
                for (int k = j + 1; k < j + x + 1; k++) {
                    //경사로가 이미 놓여져있는지 검사
                    if (checkG[i][k]) {
                        flag = false;
                        break;
                    }
                }
 
 
                //검사를 통과했다면 경사로를 놓아준다.
                if (flag) {
                    for (int k = j + 1; k < j + 1 + x; k++) {
                        checkG[i][k] = true;
                    }
                }
 
 
            }
            else {//뒷칸이 더 큰 경우
                //범위를 벗어나는 경우
                if (j + 1 - x < 0) {
                    flag = false;
                    break;
                }
 
                //경사로를 x만큼 놓을 수 있는지 검사
                for (int k = j; k > j + 1 - x; k--) {
                    if (map[i][k] != map[i][k - 1]) {
                        flag = false;
                        break;
                    }
                }
 
                for (int k = j; k > j - x; k--) {
                    if (checkG[i][k]) {
                        flag = false;
                        break;
                    }
                }
 
                //검사를 통과했다면 경사로를 놓아준다.
                if (flag) {
                    for (int k = j; k > j - x - 1; k--) {
                        checkG[i][k] = true;
                    }
                }
 
            }
 
            //활주로를 건설할 수 없다.
            if (!flag) break;
 
        }
 
        //이번행은 활주로를 건설할 수 있다.
        if (flag) cnt++;
 
    }
 
 
    return cnt;
 
}
 
 
int checkSero() {
    int cnt = 0;
 
    //모든 열을 검사
    for (int j = 0; j < n; j++) {
 
        bool flag = true;
        for (int i = 0; i < n - 1; i++) {
 
            if (map[i][j] == map[i + 1][j]) continue;
 
 
            //높이 차이를 구해준다.
            int tmp = map[i][j] - map[i + 1][j];
            if (tmp < 0) tmp = -tmp;
 
            //1보다 차이가 크면 경사로를 놓을 수 없으므로 해당 행은 활주로 건설 불가
            if (tmp > 1) {
                flag = false;
                break;
            }
 
 
            //앞쪽이 더 높은 경우 뒷쪽에 경사로 놔준다.
            if (map[i][j] > map[i + 1][j]) {
                //범위를 벗어나는 경우
                if (i + x >= n) {
                    flag = false;
                    break;
                }
 
                //경사로를 x만큼 놓을 수 있는지 검사
                for (int k = i + 1; k < i + x; k++) {
                    //높이가 같은지 검사
                    if (map[k][j] != map[k + 1][j]) {
                        flag = false;
                        break;
                    }
 
                    
                }
 
                for (int k = i + 1; k < i + x + 1; k++) {
                    //이미 놓여져있는지 검사
                    if (checkS[k][j]) {
                        flag = false;
                        break;
                    }
                }
 
 
                //검사를 통과했다면 경사로를 놓아준다.
                if (flag) {
                    for (int k = i + 1; k < i + 1 + x; k++) {
                        checkS[k][j] = true;
                    }
                }
 
 
            }
            else {
                //범위를 벗어나는 경우
                if (i + 1 - x < 0) {
                    flag = false;
                    break;
                }
 
                //경사로를 x만큼 놓을 수 있는지 검사
                for (int k = i; k > i + 1 - x; k--) {
                    if (map[k][j] != map[k - 1][j]) {
                        flag = false;
                        break;
                    }
 
                    
                }
 
                for (int k = i; k > i - x; k--) {
                    if (checkS[k][j]) {
                        flag = false;
                        break;
                    }
                }
 
                //검사를 통과했다면 경사로를 놓아준다.
                if (flag) {
                    for (int k = i; k > i - x - 1; k--) {
                        checkS[k][j] = true;
                    }
                }
 
            }
 
            if (!flag) break;
 
        }
 
        if (flag) cnt++;
 
    }
 
 
    return cnt;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        ans = 0;
        memset(checkG, false, sizeof(checkG));
        memset(checkS, false, sizeof(checkS));
 
        cin >> n >> x;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
            }
        }
        
 
        ans = checkGaro() + checkSero();
        
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 5656. [모의 SW 역량테스트] 벽돌 깨기  (0) 2019.08.06
[SWEA] 1949. [모의 SW 역량테스트] 등산로 조성  (0) 2019.08.06
[SWEA] 2115. [모의 SW 역량테스트] 벌꿀채취  (0) 2019.08.05
[SWEA] 1952. [모의 SW 역량테스트] 수영장  (0) 2019.08.05
[SWEA] 4013. [모의 SW 역량테스트] 특이한 자석  (0) 2019.07.11

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

 

3190번: 뱀

문제  'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따

www.acmicpc.net

이 문제에서 어려운 점은 뱀이 자기 몸에 부딪혀서 게임이 끝날때를 처리해주는 부분인 것 같다.

이 부분은 몸길이와 칸에 머리가 있었던 시간을 저장한 배열을 이용하면 쉽게 구할 수 있다.

 

(현재 시간 - 몸길이)가 이동할 칸에 이전에 머리가 있었던 시간보다 작으면 몸에 부딪힌 것 이다

 

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
#include <iostream>
#include <vector>
using namespace std;
 
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
 
 
int n, k;
 
//사과의 좌표를 저장
bool apple[100][100];
 
//머리가 위치한 시간을 저장
int headtime[100][100];
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
 
    cin >> n >> k;
 
    //사과정보 저장
    int ax, ay;
    for (int i = 0; i < k; i++) {
        cin >> ax >> ay;
        apple[ax - 1][ay - 1] = true;
    }
 
    int l;
    cin >> l;
    int t;
    char c;
 
    //방향 회전 정보를 저장
    vector<pair<int, char>> vt;
    for (int i = 0; i < l; i++) {
        cin >> t;
        cin >> c;
        vt.push_back(make_pair(t,c));
    }
 
    int time = 0;
 
    //방향 회전정보를 이용하기 위한 인덱스
    int index = 0;
 
    //초기 방향
    int dir = 0;
 
    //초기 길이
    int len = 1;
 
    //초기 위치는 좌측 맨위쪽
    int x = 0;
    int y = 0;
    while (true) {
        //먼저 시간증가, 길이 증가, 머리 앞칸으로 이동
        time++;
        len += 1;
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        
        //벽에 부딪힘
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) break;
 
        //몸에 부딪힘 ((현재 시간 - 몸길이)가 이동할 칸에 머리가 있었던 시간보다 작으면 몸에 부딪힌 것 이다)
        if (headtime[nx][ny] != 0 && ((time - len) < headtime[nx][ny])) break;
 
        //이동한 칸에 현재 시간을 저장
        headtime[nx][ny] = time;
 
        //사과가 있는지 검사
        if (apple[nx][ny]) {
            apple[nx][ny] = false;
        }
        else {
            len -= 1;
        }
 
 
        //l번만큼 방향이동을 한다.
        if (index < l) {
            //현재시간이 방향을 회전해야하는 시간이다
            if (time == vt[index].first) {
                if (vt[index].second == 'D') {
                    dir = (dir + 1) % 4;
                }
                else if (vt[index].second == 'L') {
                    dir = (dir + 3) % 4;
                }
 
                //방향 전환했으면 index증가 (다음 방향 정보를 이용하기 위해)
                index++;
            }
        }
        
        //현재 좌표를 머리가 이동한 칸의 좌표로 변경
        x = nx;
        y = ny;
    }
 
 
 
    cout << time << '\n';
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2234. 성곽  (0) 2019.08.13
[BOJ] 11559. Puyo Puyo  (0) 2019.08.08
[BOJ] 15683. 감시  (0) 2019.08.05
[BOJ] 14500. 테트로미노  (0) 2019.08.04
[BOJ] 14499. 주사위 굴리기  (0) 2019.08.04

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

 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할

www.acmicpc.net

CCTV구조체를 만들어서 CCTV의 좌표, 종류, 방향을 저장하게 했다.

방향은 나중에 모든 경우를 구해줄 때 저장한다.

모든 CCTV에 대해 방향을 정해줬으면 각 CCTV들의 감시 영역을 새로운 배열에 체크해주고

사각지대의 영역을 구해준다.

 

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
#include <iostream>
#include <vector>
using namespace std;
 
int n, m;
int ans;
int map[8][8];
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
 
struct CCTV {
    //감시카메라의 좌표
    int x;
    int y;
 
    //감시카메라 종류 번호
    int num;
 
    //감시할 방향 (나중에 정해준다)
    int dir;
    CCTV(int x, int y, int num) : x(x), y(y), num(num){}
};
 
vector<CCTV> vt;
 
 
//감시영역을 체크
void start(int x, int y, int dir, int newmap[8][8]) {
    while (true) {
        //dir 방향으로 계속 감시 영역을 표시한다.
        x += dx[dir];
        y += dy[dir];
 
        //범위 체크
        if (x < 0 || y < 0 || x >= n || y >= m) break;
        //벽이면 넘어갈 수 없다.
        if (map[x][y] == 6) break;
 
        //감시영역에 적당히 그냥 7넣어줬다.
        newmap[x][y] = 7;
    }
}
 
 
//모든 감시카메라들을 지정된 방향에 따라 감시영역을 표시한다.
int solve() {
    int newmap[8][8];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            newmap[i][j] = map[i][j];
        }
    }
 
    int vsize = vt.size();
    int x, y, num,dir;
    for (int i = 0; i < vsize; i++) {
        x = vt[i].x;
        y = vt[i].y;
        num = vt[i].num;
        dir = vt[i].dir;
 
        //종류에 따라서 감시영역을 표시한다.
        if (num == 1) {
            //한방향 감시
            start(x, y, dir, newmap);
        }
        else if (num == 2) {
            //반대방향이 두방향 감시
            start(x, y, dir, newmap);
            start(x, y, (dir+2)%4, newmap);
        }
        else if (num == 3) {
            //직각모양 두방향 감시
            start(x, y, dir, newmap);
            start(x, y, (dir+1)%4, newmap);
        }
        else if (num == 4) {
            //세방향 감시
            start(x, y, dir, newmap);
            start(x, y, (dir + 1) % 4, newmap);
            start(x, y, (dir + 2) % 4, newmap);
        }
        else if (num == 5) {
            //네 방향 모두 감시
            start(x, y, dir, newmap);
            start(x, y, (dir + 1) % 4, newmap);
            start(x, y, (dir + 2) % 4, newmap);
            start(x, y, (dir + 3) % 4, newmap);
        }
    }
 
 
    //처음에 사각지대였는데 감시영역을 표시한 이후에도 사각지대이면 cnt증가
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 0 && newmap[i][j] == 0) cnt++;
        }
    }
 
 
    //사각지대 수를 리턴
    return cnt;
}
 
 
//모든 감시카메라에 대해서 방향을 정해준다.
void select(int index) {
    if (index == vt.size()) {
        int tmp = solve();
 
        if (ans > tmp) ans = tmp;
        return;
    }
 
    for (int i = 0; i <= 3; i++) {
        vt[index].dir = i;
        select(index + 1);
    }
    
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
 
            //감시카메라이면 벡터에 넣는다.
            if (map[i][j] >= 1 && map[i][j] <= 5) {
                vt.push_back(CCTV( i,j,map[i][j] ));
            }
        }
    }
 
 
    //정답이 될 수 있는 값보다 큰 값을 미리 저장
    ans = 65;
    select(0);
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 11559. Puyo Puyo  (0) 2019.08.08
[BOJ] 3190. 뱀  (0) 2019.08.06
[BOJ] 14500. 테트로미노  (0) 2019.08.04
[BOJ] 14499. 주사위 굴리기  (0) 2019.08.04
[BOJ] 14503. 로봇 청소기  (0) 2019.08.04

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

먼저 두 일꾼이 선택하는 벌통이 겹치지 않도록 모든 경우를 구해준다.

두 일꾼이 벌통을 가로로 m개씩 벌통을 선택했다면 각각의 벌통에서 c를 넘지 않도록 벌꿀을 채취해서 얻는 수익의 최댓값을 구해주면 된다. 문제에 나와있듯이 수익은 벌꿀의 양을 제곱해서 더해준 값이다.

 

 

자세한 설명은 코드 참고! result 변수 대신에 수익을 나타내는 단어로 사용했으면 더 좋았을 것 같다...

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
#include <iostream>
#include <vector>
using namespace std;
 
int ans;
int n, m, c;
int honey[10][10];
bool check[10][10];
vector<int> workers[2];
 
 
//선택한 벌통에서 벌꿀을 채취한다. (sum은 벌통에 들은 꿀의 양, result는 꿀의 양을 제곱해서 얻는 수익)
int selectHoney(int worker,int index, int sum, int result) {
    //채취할 수 있는 최대 양 c를 넘어간 경우 불가능하므로 -1을 리턴
    if (sum > c) return -1;
 
    //m개의 벌통에 대해서 꿀을 채취할지 말지 모두 정해졌다.
    if (index == m) {
        return result;
    }
 
    //제곱한 결과
    int newresult = workers[worker][index] * workers[worker][index];
 
    int rt = 0;
 
    //index번째 벌통에서 꿀을 채취하는 경우
    int tmp1 = selectHoney(worker, index + 1, sum + workers[worker][index], result+newresult);
 
    //index번째 벌통에서 꿀을 채취하지 않는 경우
    int tmp2 = selectHoney(worker, index + 1, sum, result);
    
    //위 의 두가지 경우가 -1이 아니라면 더 작은 값을 리턴해준다.
    if (tmp1 != -1) rt = tmp1;
    if (tmp2 != -1 && rt < tmp2) rt = tmp2;
 
    return rt;
}
 
 
//두명의 일꾼이 벌통을 가로로 m개만큼 선택한다.
void solve(int index, int x) {
    //일꾼 두명 모두 선택이 끝났다.
    if (index > 1) {
        //두 일꾼의 벌통에서 꿀을 채취한다.
        int tmp = selectHoney(0, 0, 0, 0) + selectHoney(1, 0, 0, 0);
        if(ans < tmp) ans = tmp;
        return;
    }
 
    for (int i = x; i < n; i++) {
        for (int j = 0; j <= n-m; j++) {
            
            //현재 칸으로부터 m개의 벌통을 선택할 수 있는지 검사
            bool flag = true;
            for (int k = j; k < j + m; k++) {
                if (check[i][k]) {
                    flag = false;
                    break;
                }
            }
            //선택할 수 없다면 다음 칸으로 넘어간다.
            if (!flag) continue;
 
 
            //m개의 칸에 선택 표시를 하고 index번째 일꾼의 벌통에 넣는다.
            for (int k = j; k < j + m; k++) {
                check[i][k] = true;
                workers[index].push_back(honey[i][k]);
                
            }
 
            //다음일꾼의 경우를 탐색
            solve(index+1, i);
 
 
            //위의 탐색에서 돌아왔다면 다음 경우를 위해서 표시를 false로 바꿔주고 벡터에서도 빼준다.
            for (int k = j; k < j + m; k++) {
                check[i][k] = false;
                workers[index].pop_back();
            }
 
        }
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        ans = 0;
        cin >> n >> m >> c;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> honey[i][j];
                check[i][j] = false;
            }
        }
 
        solve(0,0);
 
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 1949. [모의 SW 역량테스트] 등산로 조성  (0) 2019.08.06
[SWEA] 4014. [모의 SW 역량테스트] 활주로 건설  (0) 2019.08.06
[SWEA] 1952. [모의 SW 역량테스트] 수영장  (0) 2019.08.05
[SWEA] 4013. [모의 SW 역량테스트] 특이한 자석  (0) 2019.07.11
[SWEA] 2105. [모의 SW 역량테스트] 디저트 카페  (0) 2019.07.11

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq&categoryId=AV5PpFQaAQMDFAUq&categoryType=CODE

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

1월부터 12월까지 모든 달에 대해서 1일권을 사용할지/1달권을 사용할지/3달권을 사용할지/ 1년권을 사용할지를

모두 해보면 되는데 1년권을 사용할 경우에는 한번에 12개월치를 다 정해주는거나 마찬가지이므로 정답에 미리 넣어놓고 다른 경우들과 비교해주면된다.

 

1일권을 이용하는 경우에는

해당 달의 이용일수X1월권 비용을 전체 비용에 더해준다.

 

1달권을 이용하는 경우에는 

해당 달에 몇번을 이용하든 상관없으므로 1달권의 비용만 더해주면 된다.

 

3달권을 이용하는 경우에는

마찬가지로 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
#include <iostream>
using namespace std;
 
int price[4];
int plan[13];
int ans;
 
void solve(int month, int sum) {
    if (month > 12) {
        if (ans > sum) ans = sum;
        return;
    }
 
 
    //이번 달에 수영장을 이용하지 않는 경우
    if (plan[month] == 0) {
        solve(month + 1, sum);
    }
    else {
 
        //1일 이용권을 사용하는 경우
        solve(month + 1, plan[month] * price[0] + sum);
        
        //1달 이용권을 사용하는 경우
        solve(month + 1, price[1] + sum);
 
        //3달 이용권을 사용하는 경우
        solve(month + 3, price[2] + sum);
 
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
 
        for (int i = 0; i < 4; i++) {
            cin >> price[i];
        }
 
        for (int j = 1; j <= 12; j++) {
            cin >> plan[j];
        }
 
        ans = price[3];
        solve(1, 0);
 
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 4014. [모의 SW 역량테스트] 활주로 건설  (0) 2019.08.06
[SWEA] 2115. [모의 SW 역량테스트] 벌꿀채취  (0) 2019.08.05
[SWEA] 4013. [모의 SW 역량테스트] 특이한 자석  (0) 2019.07.11
[SWEA] 2105. [모의 SW 역량테스트] 디저트 카페  (0) 2019.07.11
[SWEA] 5658. [모의 SW 역량테스트] 보물상자 비밀번호  (0) 2019.07.09

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

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누

www.acmicpc.net

테트로미노는 (ㅏ,ㅓ,ㅗ,ㅜ)를 제외하고 시작점으로부터 인접한 칸으로 세 번 더 이동한 모양이다.

예를 들어 밑의 그림에서 대충 저 1을 시작점으로 잡았다고 쳤을 때 아무렇게나 인접한 칸으로 네 번 이동하면

테트로미노가 된다. 즉, 모든 경우를 해보면 (ㅏ,ㅓ,ㅗ,ㅜ)를 제외한 모든 테트로미노를 만들 수 있다.

 

           
  1 2      
    3      
    4      
           
           
           
           
  1 2      
    3 4    
           
           
           

 

모든 칸에서부터 시작하여 모든 종류의 테트로미노를 만들어주면 되는데

(ㅏ,ㅓ,ㅗ,ㅜ)는 밑에 코드처럼 따로 일일이 처리해주어야 한다.

ㅡ 에서 위아래로 튀어나온 부분(?)이랑 ㅣ 에서 좌우로 튀어나온 부분을 i, j로 놓고 그 나머지 부분을 추가적으로 더해줬다. 얘네도 범위를 벗어나지 않는다면 해당 네 칸을 더해준 다음에 최댓값과 각각 비교해주면 된다.

 

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
#include <iostream>
using namespace std;
 
 
int n, m;
int ans;
int map[500][500];
bool check[500][500];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void solve(int x, int y, int sum, int cnt) {
    //테트로미노가 됐다!
    if (cnt == 4) {
        //최댓값을 비교하여 저장
        if (ans < sum) ans = sum;
        return;
    }
 
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
 
        //범위 체크
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
 
        //방문하지 않았다면 방문
        if (!check[nx][ny]) {
            check[nx][ny] = true;
            //sum에 현재 칸의 값을 더하여 넘겨준다. 현재칸을 선택했으므로 cnt도 증가
            solve(nx, ny, sum + map[nx][ny], cnt + 1);
            check[nx][ny] = false;
        }
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
 
    //모든 칸에서 모든 테트로미노를 놓는 경우를 모두 해본다.
    int sum;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            check[i][j] = true;
            solve(i, j, map[i][j], 1);
            check[i][j] = false;
 
 
            //ㅏ
            if (i - 1 >= 0 && i + 1 < n && j + 1 < m) {
                sum = map[i][j];
                sum += map[i - 1][j + 1] + map[i][j + 1] + map[i + 1][j + 1];
                if (ans < sum) ans = sum;
            }
 
 
            //ㅗ
            if (i - 1 >= 0 && j - 1 >= 0 && j + 1 < m) {
                sum = map[i][j];
                sum += map[i - 1][j - 1] + map[i - 1][j] + map[i - 1][j + 1];
                if (ans < sum) ans = sum;
            }
 
 
            //ㅓ
            if (i - 1 >= 0 && i + 1 < n && j - 1 >= 0) {
                sum = map[i][j];
                sum += map[i - 1][j - 1] + map[i][j - 1] + map[i + 1][j - 1];
                if (ans < sum) ans = sum;
            }
 
 
            //ㅜ
            if (i + 1 < n && j - 1 >= 0 && j + 1 < m) {
                sum = map[i][j];
                sum += map[i + 1][j - 1] + map[i + 1][j] + map[i + 1][j + 1];
                if (ans < sum) ans = sum;
            }
 
        }
    }
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 3190. 뱀  (0) 2019.08.06
[BOJ] 15683. 감시  (0) 2019.08.05
[BOJ] 14499. 주사위 굴리기  (0) 2019.08.04
[BOJ] 14503. 로봇 청소기  (0) 2019.08.04
[BOJ] 14502. 연구소  (0) 2019.08.04

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

 

14499번: 주사위 굴리기

첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마

www.acmicpc.net

주사위

주사위 배열을 만들어놓고 위의 그림에 나와 있는 숫자를 배열의 인덱스로 사용하였다.

즉 dice[0] 이 윗면, dice[5]가 바닥면이다.

주사위를 굴릴 때마다 배열의 값을 주사위의 해당 면에 오는 숫자로 바꿔주면 된다.

쉽게 생각하면 주사위는 그대로 있고 주사위 위의 숫자가 굴리는 방향에 따라 움직인다고 생각하면 된다.

 

굴릴 방향에 따라서 어떻게 변하는지는 그냥 일일이 해주면 되는데

예를 들어 d가 1일 경우(동쪽으로 주사위를 굴리는 경우)

위의 그림에서 3번, 0번, 2번, 5번 면의 숫자가 바뀐다. 모두 동쪽으로 한 칸씩 움직이기 때문에

0번은 2번으로, 2번은 바닥면인 5번으로, 5번에 에 있던 숫자는 3번으로, 3번에 있던 숫자는 윗면인 0으로 올라오게 된다.

이런 식으로 네 방향에 대해서 하나하나 구해주면 된다.

 

주의할 점은 범위를 벗어나는 경우에 해당 명령을 무시해야 하므로 주사위가 이동하지 않도록 해야 한다.

밑의 코드에서는 nx, ny 변수를 새로 만들어서 범위를 검사해주고 범위를 벗어나지 않으면 x, y에 넣어줬다.


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
#include <iostream>
using namespace std;
 
int dx[] = { 0,0,0,-1,1 };
int dy[] = { 0,1,-1,0,0 };
 
int map[20][20];
int dice[6];
 
int n, m, x, y, k;
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
 
    cin >> n >> m >> x >> y >> k;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    int dir;
    int nx, ny;
    while (k-- > 0) {
        cin >> dir;
 
        nx = x + dx[dir];
        ny = y + dy[dir];
 
        //범위를 벗어나면 명령을 무시
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
 
 
        if (dir == 1) {
            int tmp = dice[0];
            dice[0] = dice[3];
            dice[3] = dice[5];
            dice[5] = dice[2];
            dice[2] = tmp;
        }
        else if (dir == 2) {
            int tmp = dice[0];
            dice[0] = dice[2];
            dice[2] = dice[5];
            dice[5] = dice[3];
            dice[3] = tmp;
        }
        else if (dir == 3) {
            int tmp = dice[0];
            dice[0] = dice[4];
            dice[4] = dice[5];
            dice[5] = dice[1];
            dice[1] = tmp;
        }
        else if (dir == 4) {
            int tmp = dice[0];
            dice[0] = dice[1];
            dice[1] = dice[5];
            dice[5] = dice[4];
            dice[4] = tmp;
        }
 
 
        //지도의 칸이 0이면 주사위의 바닥면이 지도에 복사
        if (map[nx][ny] == 0) {
            map[nx][ny] = dice[5];
        }
        else {
            //그렇지 않다면 칸에 쓰여져 있는 수가 주사위 바닥면으로 복사 후에 0으로 변경
            dice[5] = map[nx][ny];
            map[nx][ny] = 0;
        }
 
 
        x = nx;
        y = ny;
 
 
        //윗면을 출력
        cout << dice[0] << '\n';
    }
 
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 15683. 감시  (0) 2019.08.05
[BOJ] 14500. 테트로미노  (0) 2019.08.04
[BOJ] 14503. 로봇 청소기  (0) 2019.08.04
[BOJ] 14502. 연구소  (0) 2019.08.04
[BOJ] 15685. 드래곤 커브  (0) 2019.08.04

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

 

14503번: 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음

www.acmicpc.net

문제에 나와있는 대로 차근차근 구현해주면 되는 시뮬레이션 문제이다.

이 문제에는 방향 전환만 주의해주면 쉽게 해결할 수 있다.

 

처음에 벽이랑 범위 벗어난 거랑 구분해야 하는 줄 알고 고생할뻔했는데 문제를 자세히 보면 모든 외곽은 벽으로 되어있기 때문에 범위 체크를 따로 해주지 않아도 된다.

 

문제에서 0인 경우에는 북쪽/ 1인 경우에는 동쪽/ 2인 경우에는 남쪽/ 3인 경우에는 서쪽이라고 주어졌으므로

그에 맞게 다음과 같이 방향 배열을 잘 저장해놓는다.

 

dx[] = { -1,0,1,0 }

dy[] = { 0,1,0,-1 }

 

청소를 하기 위해 왼쪽 방향을 보기 위해서는 (현재 방향 + 3)%4를 해주면 왼쪽 방향 index로 올 수 있다.

즉, 현재 동쪽(1)을 바라보고 있는 상황에서는 왼쪽 방향은 북쪽(0)인데 (1+3)%4 == 0으로 북쪽을 바라보게 된다.

 

후진을 하는 경우에는 북쪽을 바라보고 있었다면 남쪽 방향으로, 남쪽을 바라보고 있었다면 북쪽으로 이동하면 된다.

마찬가지로 동에서 서, 서에서 동으로 이동해주면 된다.

즉, 0에서 2, 2에서 0, 1에서 3, 3에서 1 이므로 위와 비슷하게 (현재 방향+2)%4를 해주면 된다.

 

 

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
#include <iostream>
using namespace std;
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
int n, m;
int map[50][50];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    int r, c, dir;
    cin >> r >> c >> dir;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    int cnt = 0;
    while (true) {
        //현재 위치 청소
        if (map[r][c] == 0) {
            map[r][c] = 2;
            cnt++;
        }
 
 
        //네 방향 모두 청소가 이미 되어있거나 벽인 경우
        if (map[r - 1][c] != 0 && map[r + 1][c] != 0 && map[r][c - 1] != 0 && map[r][c + 1] != 0) {
            
            //후진
            r += dx[(dir + 2) % 4];
            c += dy[(dir + 2) % 4];
 
            //뒤쪽 방향이 벽이라 후진도 할 수 없는 경우
            if (map[r][c] == 1) {
                //작동 중지
                break;
            }
            else {
                continue;
            }
        }
 
 
        //현재 방향의 왼쪽 방향
        dir = (dir + 3) % 4;
 
        //왼쪽 방향에 청소하지 않은 공간이 존재한다.
        if (map[r + dx[dir]][c + dy[dir]] == 0) {
            //해당방향으로 전진
            r += dx[dir];
            c += dy[dir];
        }
        else {
            continue;
        }
 
 
    }
 
    cout << cnt << '\n';
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 14500. 테트로미노  (0) 2019.08.04
[BOJ] 14499. 주사위 굴리기  (0) 2019.08.04
[BOJ] 14502. 연구소  (0) 2019.08.04
[BOJ] 15685. 드래곤 커브  (0) 2019.08.04
[BOJ] 15686. 치킨 배달  (0) 2019.08.04

+ Recent posts

티스토리툴바