백준 14500번 테트로미노
문제 링크 : https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 꼭짓점끼리 연결되어 있어야 한다. 즉, 변과 꼭짓점이 맞닿아있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어
www.acmicpc.net
처음엔 대칭도 가능하다는 것을 못보고 맞왜틀 하고있었는데
대칭이 가능하단걸 알고 추가 해주니 맞았다.
문제 접근
1. 3차원배열에 가능한 테트노미로의 모양을 다 저장해놓았다.
ttrmn[19][5][2]
- 19 : 가능한 도형의 모양 9개
- 5 : 블럭4개 + 그 도형의 세로, 가로길이를 넣어줄 마지막 인덱스 1개
- 2 : y좌표, x좌표
2. 반복문으로 모든 경우의 수의 합을 구하고 그중 가장 큰 값 출력하였다.
소스코드
|
#include <iostream>
using namespace std;
int n, m, max_sum = 0; int map[500][500];
int ttrmn[19][5][2] = {
{ {0,0}, {0,1}, {1,0}, {1,1}, {2,2} },
{ {0,0}, {0,1}, {0,2}, {0,3}, {1,4} }, { {0,0}, {1,0}, {2,0}, {3,0}, {4,1} },
{ {0,0}, {1,0}, {2,0}, {2,1}, {3,2} }, { {0,0}, {0,1}, {0,2}, {1,0}, {2,3} }, { {0,0}, {0,1}, {1,1}, {2,1}, {3,2} }, { {0,2}, {1,0}, {1,1}, {1,2}, {2,3} },
{ {0,1}, {1,1}, {2,0}, {2,1}, {3,2} }, { {0,0}, {1,0}, {1,1}, {1,2}, {2,3} }, { {0,0}, {0,1}, {1,0}, {2,0}, {3,2} }, { {0,0}, {0,1}, {0,2}, {1,2}, {2,3} },
{ {0,0}, {1,0}, {1,1}, {2,1}, {3,2} }, { {0,1}, {0,2}, {1,0}, {1,1}, {2,3} }, { {0,1}, {1,0}, {1,1}, {2,0}, {3,2} }, { {0,0}, {0,1}, {1,1}, {1,2}, {2,3} },
{ {0,0}, {0,1}, {0,2}, {1,1}, {2,3} }, { {0,1}, {1,0}, {1,1}, {2,1}, {3,2} }, { {0,1}, {1,0}, {1,1}, {1,2}, {2,3} }, { {0,0}, {1,0}, {1,1}, {2,0}, {3,2} }
};
int main() { cin >> n >> m;
for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; } }
for (int t = 0; t < 19; t++) { for (int i = 0; i < n - ttrmn[t][4][0] + 1; i++) { for (int j = 0; j < m - ttrmn[t][4][1] + 1; j++) { int sum = 0; for (int k = 0; k < 4; k++) { sum += map[i + ttrmn[t][k][0]][j + ttrmn[t][k][1]]; } if (max_sum < sum) max_sum = sum; } } }
cout << max_sum;
} |