백준 14500번 테트로미노

 

문제 링크 : https://www.acmicpc.net/problem/14500

14500번: 테트로미노

 

 

처음엔 대칭도 가능하다는 것을 못보고 맞왜틀 하고있었는데

대칭이 가능하단걸 알고 추가 해주니 맞았다.

 

문제 접근

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;   }