문제 링크입니다 https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
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
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
|
// [백준] 삼성 SW 역량 테스트 기출 문제 : 테트로미노(14500)
#include<cstdio>
const int MAX = 500 + 10;
int n, m, ret, paper[MAX][MAX];
const char tetromino[19][4][5] = {
{
"1111",
"0000",
"0000",
"0000",
},
{
"1000",
"1000",
"1000",
"1000",
},
{
"1100",
"1100",
"0000",
"0000",
},
{
"1000",
"1000",
"1100",
"0000",
},
{
"1110",
"1000",
"0000",
"0000",
},
{
"1100",
"0100",
"0100",
"0000",
},
{
"0010",
"1110",
"0000",
"0000",
},
{
"0100",
"0100",
"1100",
"0000",
},
{
"1000",
"1110",
"0000",
"0000",
},
{
"1100",
"1000",
"1000",
"0000",
},
{
"1110",
"0010",
"0000",
"0000",
},
{
"1000",
"1100",
"0100",
"0000",
},
{
"0110",
"1100",
"0000",
"0000",
},
{
"0100",
"1100",
"1000",
"0000",
},
{
"1100",
"0110",
"0000",
"0000",
},
{
"1110",
"0100",
"0000",
"0000",
},
{
"0100",
"1100",
"0100",
"0000",
},
{
"0100",
"1110",
"0000",
"0000",
},
{
"1000",
"1100",
"1000",
"0000",
}
};
// k번째 테트로미노를 놓았을 때 놓인 칸에 쓰인 수들의 합을 반환하는 함수
int getSum(int y, int x, int k) {
int sum = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++) {
if (tetromino[k][i][j] - '0' && (i + y >= n || j + x >= m)) {
return -1; // 테트로미노를 놓았는데 입력받은 배열의 범위를 넘으면
}
sum += (tetromino[k][i][j] - '0') * paper[i + y][j + x];
}
return sum;
}
void solve(void) {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &paper[i][j]);
// 배열 전체를 탐색하며 최댓값을 찾는다
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int k = 0; k < 19; k++) {
int result = getSum(i, j, k);
if (ret < result) ret = result;
}
printf("%d", ret);
}
int main(void) {
solve();
return 0;
}
|
cs |
'알고리즘 > BaekJoon' 카테고리의 다른 글
| 백준 1260 : DFS와 BFS (0) | 2020.02.19 |
|---|---|
| 백준 1996 : 프린터 큐 (0) | 2020.02.19 |
| 백준 14889 : 스타트와 링크 (0) | 2020.02.18 |
| 백준 16234 : 인구 이동 (0) | 2020.02.18 |
| 백준 1018 : 체스판 다시 칠하기 (0) | 2020.02.18 |