Dev.CodingTest/BACKJOON
[백준 c++] 14500번 테트로미노
zeekke
2020. 4. 26. 02:38
문제 링크입니다.
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
풀이 방법
브루트포스 알고리즘을 사용합니다.
테트로미노는 5개의 모양를 가지지만 상하좌우 방향을 달리함에 따라 19개의 모양을 가집니다.
이러한 19개의 모양을 shape 배열에 저장해놓고,
모든 칸을 순회하며 각 칸에 19개의 모양을 대입합니다.
순회를 진행하면서 각 모양마다 속한 칸의 숫자들을 더하고 비교 연산을 통해 최댓값을 구합니다.
풀이
//
// main.cpp
// 14500
//
// Created by Jihye on 2020/04/26.
// Copyright © 2020 Jihye Han. All rights reserved.
//
#include <iostream>
using namespace std;
int n, m; // 행, 열의 크기
int board[500][500]; // 종이
int ans = 0; // 최대합
const int shape[19][4][2] = {
{ {0,0}, {0,1}, {1,0}, {1,1} },
{ {0,0}, {0,1}, {0,2}, {0,3} },
{ {0,0}, {1,0}, {2,0}, {3,0} },
{ {0,0}, {0,1}, {0,2}, {1,0} },
{ {0,2}, {1,0}, {1,1}, {1,2} },
{ {0,0}, {1,0}, {1,1}, {1,2} },
{ {0,0}, {0,1}, {0,2}, {1,2} },
{ {0,0}, {1,0}, {2,0}, {2,1} },
{ {0,0}, {0,1}, {1,1}, {2,1} },
{ {0,0}, {0,1}, {1,0}, {2,0} },
{ {0,1}, {1,1}, {2,0}, {2,1} },
{ {0,0}, {1,0}, {1,1}, {2,1} },
{ {0,1}, {1,0}, {1,1}, {2,0} },
{ {0,1}, {0,2}, {1,0}, {1,1} },
{ {0,0}, {0,1}, {1,1}, {1,2} },
{ {0,0}, {0,1}, {0,2}, {1,1} },
{ {0,1}, {1,0}, {1,1}, {1,2} },
{ {0,1}, {1,0}, {1,1}, {2,1} },
{ {0,0}, {1,0}, {1,1}, {2,0} }
};
void tetromino(int x, int y) {
// 19개의 테트로미노 모양 대입하기
for (int i = 0; i < 19; i++) {
int temp = 0;
for (int j = 0; j < 4; j++) {
int tx = x + shape[i][j][0];
int ty = y + shape[i][j][1];
if (tx >= 0 && tx < n && ty >= 0 && ty < m) {
temp += board[tx][ty];
}
}
if (ans < temp) ans = temp;
}
}
void solve() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
tetromino(i, j);
}
}
printf("%d\n", ans);
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &board[i][j]);
}
}
solve();
return 0;
}