14500 테트로미노

14500 테트로미노 (c++)

문제

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

접근 방식

브루트포스, 도형

1. 테트리스 도형들의 몇가지 공통점을 찾았다.
   1. 2*3 도형에서 2개를 빼서 만들어지는 도형
   2. 3*2 도형에서 2개를 빼서 만들어지는 도형
   3. 2*2 도형
   4. 1*4 도형
   5. 4*1 도형
2. 여기서 핵심은 23과 32를 미리 구해놓고 각각 2개씩 빼가면서 최대값을 비교한다는 것이다.
   • 불필요한 덧셈을 줄일 수 있었다.

문제 풀이

#include <iostream>
using namespace std;
inline short Max(short a, short b) { return a > b ? a : b; }
short N, M;
short arr[500][500];
short totalMax = 0;
void Func(short y, short x)
{
    short curMax = 0, sum;
    // 1) 2 * 3
    if (y + 1 < N && x + 2 < M)
    {
        sum = arr[y][x] + arr[y][x + 1] + arr[y][x + 2] + arr[y + 1][x] + arr[y + 1][x + 1] + arr[y + 1][x + 2];
        // 1) 01
        curMax = Max(curMax, sum - arr[y][x] - arr[y][x + 1]);
        // 2) 12
        curMax = Max(curMax, sum - arr[y][x + 1] - arr[y][x + 2]);
        // 3) 34
        curMax = Max(curMax, sum - arr[y + 1][x] - arr[y + 1][x + 1]);
        // 4) 45
        curMax = Max(curMax, sum - arr[y + 1][x + 1] - arr[y + 1][x + 2]);
        // 5) 05
        curMax = Max(curMax, sum - arr[y][x] - arr[y + 1][x + 2]);
        // 6) 23
        curMax = Max(curMax, sum - arr[y][x + 2] - arr[y + 1][x]);
        // 7) 02
        curMax = Max(curMax, sum - arr[y][x] - arr[y][x + 2]);
        // 8) 35
        curMax = Max(curMax, sum - arr[y + 1][x] - arr[y + 1][x + 2]);
    }
    // 2) 3 * 2
    if (y + 2 < N && x + 1 < M)
    {
        sum = arr[y][x] + arr[y + 1][x] + arr[y + 2][x] + arr[y][x + 1] + arr[y + 1][x + 1] + arr[y + 2][x + 1];
        // 1) 02
        curMax = Max(curMax, sum - arr[y][x] - arr[y + 1][x]);
        // 2) 24
        curMax = Max(curMax, sum - arr[y + 1][x] - arr[y + 2][x]);
        // 3) 13
        curMax = Max(curMax, sum - arr[y][x + 1] - arr[y + 1][x + 1]);
        // 4) 35
        curMax = Max(curMax, sum - arr[y + 1][x + 1] - arr[y + 2][x + 1]);
        // 5) 05
        curMax = Max(curMax, sum - arr[y][x] - arr[y + 2][x + 1]);
        // 6) 14
        curMax = Max(curMax, sum - arr[y][x + 1] - arr[y + 2][x]);
        // 7) 04
        curMax = Max(curMax, sum - arr[y][x] - arr[y + 2][x]);
        // 8) 15
        curMax = Max(curMax, sum - arr[y][x + 1] - arr[y + 2][x + 1]);
    }
    // 3) 2 * 2
    if (y + 1 < N && x + 1 < M)
    {
        sum = arr[y][x] + arr[y][x + 1] + arr[y + 1][x] + arr[y + 1][x + 1];
        curMax = Max(curMax, sum);
    }
    // 4) 1 * 4
    if (y + 3 < N)
    {
        sum = arr[y][x] + arr[y + 1][x] + arr[y + 2][x] + arr[y + 3][x];
        curMax = Max(curMax, sum);
    }
    if (x + 3 < M)
    {
        sum = arr[y][x] + arr[y][x + 1] + arr[y][x + 2] + arr[y][x + 3];
        curMax = Max(curMax, sum);
    }
    totalMax = Max(curMax, totalMax);
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for (short i = 0; i < N; ++i)
    {
        for (short j = 0; j < M; ++j)
        {
            cin >> arr[i][j];
        }
    }

    for (short i = 0; i < N; ++i)
    {
        for (short j = 0; j < M; ++j)
        {
            Func(i, j);
        }
    }

    cout << totalMax << "\n";

    return 0;
}

다시 생각해볼 점

1. 도형의 칸수가 적기 때문에 for문을 돌리지 않고 직접 더하고 빼는게 효율적이라 생각했다.
2. inline Max 함수를 만들어 사용함으로써 시간을 줄였다.
3. 23, 32 도형의 공통점을 찾아서 연산 시간을 줄였다.
4. 어떻게 자르던 4칸짜리 도형이고, 한 칸에 1’000을 넘지 않기 때문에 최대값이 4’000 이라 자료형을 int 에서 short 로 줄였더니 메모리 사용량과 시간이 현저하게 줄었다.
5. 무려 7등에 안착했다. 10등 이내는 처음인 것 같다.
6. 앞으로 문제에 맞는 적절한 자료형을 사용하는데에 더 주의를 기울여야겠다.