문제 해결/BOJ
[BOJ] 14500 테트르미노
자잘
2019. 8. 17. 14:04
문제 출처: https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
1X1 정사각형 네개를 이어 붙혀서 만들 수 있는 모양으로 칸을 덮었을 때 덮혀진 칸들의 값의 총합이 가장 클 때를 구하는 문제입니다. 종만북에서 BOARDCOVER문제를 풀고 생각이 나서 풀었습니다. 종만북을 보기 전에는 구현이 복잡할 것같아서 그냥 포기했었는데 BOARDCOVER에서 모양을 배열로 저장하는 방법을 통해서 쉽게 구현할 수 있었습니다. 전형적인 부루트 포스문제로 4개의 정사각형의 만들 수 있는 모양 총 19개이며 최대 500X500개의 칸에 대해서 검사를 되고 범위 조건에 의해 4 X 19 X 500 X 500 번의 수행보다 적은 수행 시간으로 구할 수 있습니다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<iostream> | |
| using namespace std; | |
| int tetro[19][3][2] = | |
| { | |
| {{1,0},{2,0},{3,0}}, | |
| {{0,1},{0,2},{0,3}}, | |
| {{0,1},{1,0},{1,1}}, | |
| {{1,0},{2,0},{2,1}}, | |
| {{0,1},{-1,1},{-2,1}}, | |
| {{1,0},{2,0},{0,1}}, | |
| {{0,1},{1,1},{2,1}}, | |
| {{1,0},{1,1},{2,1}}, | |
| {{1,0},{0,1},{-1,1}}, | |
| {{0,1},{-1,1},{-1,2}}, | |
| {{0,1},{1,1},{1,2}}, | |
| {{0,1},{0,2},{-1,1}}, | |
| {{1,0},{2,0},{1,1}}, | |
| {{0,1},{0,2},{1,1}}, | |
| {{0,1},{-1,1},{1,1}}, | |
| {{1,0},{0,1},{0,2}}, | |
| {{1,2},{0,1},{0,2}}, | |
| {{1,0},{1,1},{1,2}}, | |
| {{0,1},{0,2},{-1,2}} | |
| }; | |
| //4개의 칸으로 만들 수 있는 모양 | |
| int N, M, ans; | |
| int map[500][500]; | |
| bool InRange(int y, int x) | |
| { | |
| return 0 <= x && x < M && 0 <= y && y < N; | |
| } | |
| void check(int y, int x, int type) | |
| { | |
| int temp = map[y][x]; | |
| for (int i = 0; i < 3; i++) | |
| { | |
| int ny = y + tetro[type][i][0]; | |
| int nx = x + tetro[type][i][1]; | |
| if (!InRange(ny, nx)) | |
| return; | |
| temp += map[ny][nx]; | |
| } | |
| ans = (ans < temp) ? temp : ans; | |
| } | |
| int main(void) | |
| { | |
| ios_base::sync_with_stdio(false); cin.tie(NULL); | |
| 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; i++) | |
| { | |
| for (int j = 0; j < M; j++) | |
| { | |
| for (int t = 0; t < 19; t++) | |
| { | |
| check(i, j, t); | |
| } | |
| } | |
| } | |
| cout << ans; | |
| } |