14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
처음엔 경우의 수를 적게 생각하고 풀어서 계속 틀린 문제이다.
천천히 대칭을 포함한 경우의 수 19가지를 생각하고 그에 맞게 최대값을 구해주었다.
나 같은 경우에는 크게 5가지로 나누었다.
네모 모양 1가지 경우의 수를 계산하고
3개짜리 테트리스에 1개를 모든 방향에 붙인다는 생각으로 크게 2가지, 작게 7가지씩 14가지를 구성하였고
또한 2개짜리에 2개를 붙이는 경우를 2개씩 총 4가지를 계산해주었다.
#define _CRT_SECURE_NO_WARINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int map[501][501];
int N, M, ans, temp;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
}
}
for (int i = 0; i < N - 1; i++) { // 네모모양 계산
for (int j = 0; j < M - 1; j++) {
ans = max(ans, map[i][j] + map[i + 1][j + 1] + map[i + 1][j] + map[i][j + 1]);
}
}
for (int i = 0; i < N - 2; i++) { //세로 3개짜리에 1개 붙이기
for (int j = 0; j < M; j++) {
temp = map[i][j] + map[i + 1][j] + map[i + 2][j];
if (i + 3 < N) {
ans = max(ans, temp + map[i + 3][j]);
}
if (j - 1 >= 0) {
ans = max(ans, temp + map[i][j - 1]);
ans = max(ans, temp + map[i + 1][j - 1]);
ans = max(ans, temp + map[i + 2][j - 1]);
}
if (j + 1 < M) {
ans = max(ans, temp + map[i][j + 1]);
ans = max(ans, temp + map[i + 1][j + 1]);
ans = max(ans, temp + map[i + 2][j + 1]);
}
}
}
for (int i = 0; i < N; i++) { //가로 3개짜리에 1개 붙이기
for (int j = 0; j < M - 2; j++) {
temp = map[i][j] + map[i][j + 1] + map[i][j + 2];
if (j + 3 < M) {
ans = max(ans, temp + map[i][j + 3]);
}
if (i - 1 >= 0) {
ans = max(ans, temp + map[i - 1][j]);
ans = max(ans, temp + map[i - 1][j + 1]);
ans = max(ans, temp + map[i - 1][j + 2]);
}
if (i + 1 < N) {
ans = max(ans, temp + map[i + 1][j]);
ans = max(ans, temp + map[i + 1][j + 1]);
ans = max(ans, temp + map[i + 1][j + 2]);
}
}
}
for (int i = 0; i < N - 2; i++) { //세로 2개짜리에 2개 붙이기
for (int j = 0; j < M; j++) {
temp = map[i][j] + map[i + 1][j];
if (j - 1 >= 0) {
ans = max(ans, temp + map[i+1][j - 1] + map[i + 2][j - 1]);
}
if (j + 1 < M) {
ans = max(ans, temp + map[i+1][j + 1] + map[i + 2][j + 1]);
}
}
}
for (int i = 0; i < N; i++) { //가로 2개짜리에 2개 붙이기
for (int j = 0; j < M - 2; j++) {
temp = map[i][j] + map[i][j + 1];
if (i + 1 < N) {
ans = max(ans, temp + map[i + 1][j + 1] + map[i + 1][j + 2]);
}
if (i - 1 >= 0) {
ans = max(ans, temp + map[i - 1][j + 1] + map[i - 1][j + 2]);
}
}
}
cout << ans << "\n";
}'알고리즘 공부 > C++' 카테고리의 다른 글
| [C++] 백준 14499번: 주사위 굴리기 (0) | 2021.03.26 |
|---|---|
| [C++] 백준 16234번: 인구 이동 (0) | 2021.03.25 |
| [C++] 백준 3190번: 뱀 (0) | 2021.03.19 |
| [C++] 백준 13458번: 시험 감독 (0) | 2021.03.17 |
| [C++] 백준 1992번: 쿼드트리 (0) | 2020.11.30 |