백준 14500 테트로미노

어렵다곳 생각하지말고 문제부터 천천히 읽는다.

대충 읽다가 폴리오미노, 테트로미노가 뭔지 제대로 모르고 풀고 있었다.

테트로미노는 위 사진에서 나오는 각각의 도형이다.

그리고 문제에서 구해야 하는 것을 제대로 읽지 않았는데, 테트로미노 5종류 중 하나를 놓았을 때 최대값을 구하는 것이다.(대칭 및 돌려서 나오는 모양도 포함 총 19가지)

다음으로 시간제한을 본다.

도형을 돌려서 만들 수 있는 모든 경우의 수는 19가지이다. 그리고 N*M 안에 넣어야 하므로 19 *  500^2이 경우의 수의 최대값이다.

천만을 넘지 않으므로 브루트포스로 풀 수 있다.

모든 경우의 수를 어떻게 돌려보아야 할까?

테트로미노의 한 블럭을 기준으로 해서 모든 경우의 수를 돌려본다.

코드가 복잡해지므로, 3차원 배열을 이용해서 테트로미노의 모든 형태를 저장한 후 for문으로 처리한다.

3차원 배열의 모양은 기준점을 잡는 것에 따라 사람마다 다르게 작성할 수 있다.

기준점으로부터 row와 column이 1씩 증가하면 {1,1}이라 생각한다. 즉, 인덱스에 더해줄 값을 배열로 처리한다고 생각하면 된다.

0	1
	2
4	3

                                                                                                               2번  3번  4번 

예를 들어 위와 같은 테트로미노가 있다고 했을 때 기준점은 1번 블럭이 되고 차례로, {{1,0},{2,0},{2,-1}}이 될 것이다.

3차원 배열을 작성하는 데 실수하지 않도록 주의한다.

#include <iostream>

using namespace std;

//19종류 기준점 제외 3개의 블럭, 좌표(i,j)2개

int tetromino[19][3][2] = {

    

    //긴 작대기 경우의 수 2개

    { { 0,1 },{ 0,2 },{ 0,3 } },

    { { 1,0 },{ 2,0 },{ 3,0 } },

    //정사각형 1개

    { { 1,0 },{ 0,1 },{ 1,1 } },

    //ㄴ자 경우의 수 8개

    { { 1,0 },{ 2,0 },{ 2,1 } },//밑으로 긴 ㄴ

    { { 1,0 },{ 2,0 },{ 2,-1 } },//밑으로 긴 ┘

    { { 0,1 },{ 0,2 },{ 1,0 } },//오른쪽으로 긴 ┌

    { { 1,0 },{ 1,1 },{ 1,2 } },//오른쪽으로 긴 ㄴ

    { { 0,1 },{ 1,1 },{ 2,1 } },//밑으로 긴 ┐

    { { 0,1 },{ 1,0 },{ 2,0 } },//밑으로 긴 ┌

    { { 0,1 },{ 0,2 },{ 1,2 } },//왼쪽으로 긴 ┐

    { { 0,1 },{ 0,2 },{ -1,2 } },//왼쪽으로 긴 ┘

    //번개 모양 경우의 수 4개

    { { 1,0 },{ 1,1 },{ 2,1 } },

    { { 1,0 },{ 1,-1 },{ 2,-1 } },

    { { 0,1 },{ -1,1 },{ -1,2 } },

    { { 0,1 },{ 1,1 },{ 1,2 } },

    //ㅗ 모양 경우의 수 4개

    { { 0,1 },{ -1,1 },{ 0,2 } },//ㅗ

    { { 0,1 },{ 1,1 },{ 0,2 } },//ㅜ

    { { -1,0 },{ 1,0 },{ 0,1 } },//ㅏ

    { { 0,1 },{ -1,1 },{ 1,1 } }//ㅓ

                                /*

    //긴 막대기 경우의 수 2개

    { { 0,1 },{ 0,2 },{ 0,3 } },//서있는 거

    { { 1,0 },{ 2,0 },{ 3,0 } },//누운 거

    //ㄴ자 경우의 수 8개

    { { 1,0 },{ 2,0 },{ 2,1 } },//밑으로 긴 ㄴ

    { { 1,0 },{ 2,0 },{ 2,-1 } },//밑으로 긴 ┘

    { { 0,1 },{ 0,2 },{ 1,0 } },//오른쪽으로 긴 ┌

    { { 1,0 },{ 1,1 },{ 1,2 } },//오른쪽으로 긴 ㄴ

    { { 0,1 },{ 1,1 },{ 2,1 } },//밑으로 긴 ┐ ==> 이거 틀려서 틀렸다고 나옴 {1,2}로 적었다가 틀림

    { { 0,1 },{ 1,0 },{ 2,0 } },//밑으로 긴 ┌

    { { 0,1 },{ 0,2 },{ 1,2 } },//왼쪽으로 긴 ┐

    { { 0,1 },{ 0,2 },{ -1,2 } },//왼쪽으로 긴 ┘

    //정사각형

    { { 0,1 },{ 1,0 },{ 1,1 } },

    //번개 모양 경우의 수 4개

    { { 0,1 },{ -1,1 },{ -1,2 } },

    { { 1,0 },{ 1,1 },{ 2,1 } },

    { { 0,1 },{ 1,1 },{ 1,2 } },

    { { 1,0 },{ 1,-1 },{ 2,-1 } },

    //ㅗ 모양 경우의 수 4개

    { { 0,1 },{ 0,2 },{ -1,1 } },//ㅗ

    { { 0,1 },{ 0,2 },{ 1,1 } },//ㅜ

    { { 1,0 },{ 2,0 },{ 1,1 } },//ㅏ

    { { 1,0 },{ 2,0 },{ 1,-1 } },//ㅓ

    */

};

int ar[500][500];

int main(int argc, char** argv) {

    int n, m, max = 0;

    cin >> n >> m;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < m; j++) {

            cin >> ar[i][j];

        }

    }

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < m; j++) {

            for (int k = 0; k < 19; k++) {

                int ok = true;

                int sum = ar[i][j];//기준이 되는 블럭은 sum에 미리 더해준다.

                for (int l = 0; l < 3; l++) {//나머지 3개의 블럭이 종이안에 들어오는지 검사한다. 들어오면 sum에 더해준다.

                    if (i + tetromino[k][l][0] >= 0 && i + tetromino[k][l][0] < n && j + tetromino[k][l][1] >= 0 && j + tetromino[k][l][1] < m) {

                        sum += ar[i + tetromino[k][l][0]][j + tetromino[k][l][1]];

                    }

                    else {//들어오지 않는 블럭이 있으면 false

                        ok = false;

                        break;

                    }

                }

                if (ok == true) {//나머지 3개의 블럭이 모두 종이안에 들어오면 sum과 max값을 비교한다.

                    if (sum > max) max = sum;

                }

            }

        }

    }

    printf("%d\n", max);

    return 0;

}

출처: https://www.acmicpc.net/problem/14500