문제
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
소스코드
#include <iostream>
using namespace std;
int a[500][500];
int block[19][3][2] = {
{{0,1}, {0,2}, {0,3}},
{{1,0}, {2,0}, {3,0}},
{{1,0}, {1,1}, {1,2}},
{{0,1}, {1,0}, {2,0}},
{{0,1}, {0,2}, {1,2}},
{{1,0}, {2,0}, {2,-1}},
{{0,1}, {0,2}, {-1,2}},
{{1,0}, {2,0}, {2,1}},
{{0,1}, {0,2}, {1,0}},
{{0,1}, {1,1}, {2,1}},
{{0,1}, {1,0}, {1,1}},
{{0,1}, {-1,1}, {-1,2}},
{{1,0}, {1,1}, {2,1}},
{{0,1}, {1,1}, {1,2}},
{{1,0}, {1,-1}, {2,-1}},
{{0,1}, {0,2}, {-1,1}},
{{0,1}, {0,2}, {1,1}},
{{1,0}, {2,0}, {1,1}},
{{1,0}, {2,0}, {1,-1}},
};
int main() {
int n, m;
cin >> n >> m;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
cin >> a[i][j];
}
}
int ans = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
for (int k=0; k<19; k++) {
bool ok = true;
int sum = a[i][j];
for (int l=0; l<3; l++) {
int x = i+block[k][l][0];
int y = j+block[k][l][1];
if (0 <= x && x < n && 0 <= y && y < m) {
sum += a[x][y];
} else {
ok = false;
break;
}
}
if (ok && ans < sum) {
ans = sum;
}
}
}
}
cout << ans << '\n';
return 0;
}해설
경우의 수 총 19가지
대칭하거나 돌려서 나올 수 있는 블럭을 미리 저장해놓고 모든 경우의 수를 다 해본다.
'Algorithm > brute force' 카테고리의 다른 글
| [백준] C++ 알고리즘 1748번 - 수 이어 쓰기 1문제 (0) | 2021.05.30 |
|---|---|
| [백준] C++ 알고리즘 6064번 - 카잉 달력 문제 (0) | 2021.05.28 |
| [백준] C++ 알고리즘 1107번 - 리모컨 문제 (0) | 2021.05.28 |
| [백준] c++ 알고리즘 1476번 - 날짜 계산 문제 (0) | 2021.05.27 |
| [백준] C++ 알고리즘 3085번 - 사탕 게임 문제 (0) | 2021.05.27 |
