[삼성 기출 문제] 백준 14500 테트로미노

문제 링크

클릭시 이동합니다.

어떻게 풀까?

블럭들을 보시면 최대 4x4 영역 안에 들어온다는 것을 알 수 있습니다.

간단하게, 4x4 영역 안에 블럭에 들어오는 영역이면 1, 아니면 0으로 표시하면,

모든 (i,j) 영역에 대해서 위에서 저장한 값을 곱해서 더하면 블럭에 대한 더하기 값을 알 수 있습니다.

이 중 최댓값을 반환하면 되겠죠!

다만 위처럼 배열 인덱스 초과가 나지 않도록 하기위해, 오른쪽과 아래에 0의 값을 가지도록 영역을 더 넓혀서 계산합시다!

테트로미노 사전을 만드는 것이 문제 푸는것 보다 오래 걸리는 문제입니다.

코드

#include<iostream>
#include<cstring>
#include<cstdio>
 
using namespace std;
 
struct TetInfo
{
    int blocks[5][8][16] = 
    {
        {
            {
                1,1,1,1,
                0,0,0,0,
                0,0,0,0,
                0,0,0,0
            },
            {
                1,0,0,0,
                1,0,0,0,
                1,0,0,0,
                1,0,0,0
            }
        },
 
        {
            {
                1,1,0,0,
                1,1,0,0,
                0,0,0,0,
                0,0,0,0
            }
        },
 
        {
            {
                1,0,0,0,
                1,0,0,0,
                1,1,0,0,
                0,0,0,0
            },
            {
                1,1,1,0,
                1,0,0,0,
                0,0,0,0,
                0,0,0,0
            },
            {
                1,1,0,0,
                0,1,0,0,
                0,1,0,0,
                0,0,0,0
            },
            {
                0,0,1,0,
                1,1,1,0,
                0,0,0,0,
                0,0,0,0
            },
            {
                0,1,0,0,
                0,1,0,0,
                1,1,0,0,
                0,0,0,0
            },
            {
                1,0,0,0,
                1,1,1,0,
                0,0,0,0,
                0,0,0,0
            },
            {
                1,1,0,0,
                1,0,0,0,
                1,0,0,0,
                0,0,0,0
            },
            {
                1,1,1,0,
                0,0,1,0,
                0,0,0,0,
                0,0,0,0
            }
        },
        {
            {
                1,0,0,0,
                1,1,0,0,
                0,1,0,0,
                0,0,0,0
            },
            {
                0,1,1,0,
                1,1,0,0,
                0,0,0,0,
                0,0,0,0
            },
            {
                0,1,0,0,
                1,1,0,0,
                1,0,0,0,
                0,0,0,0,
            },
            {
                1,1,0,0,
                0,1,1,0,
                0,0,0,0,
                0,0,0,0
            }
        },
        {
            {
                0,1,0,0,
                1,1,0,0,
                0,1,0,0,
                0,0,0,0
            },
            {
                1,1,1,0,
                0,1,0,0,
                0,0,0,0,
                0,0,0,0
            },
            {
                0,1,0,0,
                1,1,1,0,
                0,0,0,0,
                0,0,0,0
            },
            {
                1,0,0,0,
                1,1,0,0,
                1,0,0,0,
                0,0,0,0
            }
        }
    };
    int blockNum[5] = {2,1,8,4,4};
    int map[503][503];
 
    int n, m;
    void init()
    {
        memset(map,0,sizeof(map));
        scanf("%d %d\n", &n, &m);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                scanf("%d", &map[i][j]);
    }
 
    int getMax()
    {
        int max = -1;
        for(int r = 0 ; r < n; r++)
        {
            for(int c = 0 ; c < m ; c++)
            {
                for(int i = 0; i < 5; i++)
                {
                    for(int j = 0; j < blockNum[i]; j++)
                    {
                        int sum = 0;
                        for(int row = 0; row < 4; row++)
                        {
                            for(int col = 0; col < 4; col++)
                            {
                                sum = blocks[i][j][row*4+col] ? sum + map[r+row][c+col] : sum;
                            }
                        }
                        max = max < sum ? sum : max;
                    }
                }
            }
        }
 
        return max;
    }
} info;
 
int main()
{
    info.init();
    int res = info.getMax();
    printf("%d\n", res);
    return 0;
}

시간 복잡도

맵 전체를 훑어보기 때문에 시간복잡도는 입니다.