[백준_14500(테트로미노)]

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

14500번: 테트로미노

문제 설명

 

문제 풀이

• 대칭 및 회전을 통해 만들 수 있는 모양의 종류는 다음과 같다.

• 세로 크기 N과 가로 크기 M (4 ≤ N, M ≤ 500)이고 가능한 모양은 19개 이다.
• 따라서, 시간 복잡도는 O(NM19)로 모든 시뮬레이션을 구현하기에 충분한 시간이다.

본인은 1,2,3,4,5번 모양을 각각 함수로 만들어서 풀이했는데 이는 실수를 많이 유발했다.특히 5번

이런 경우는 그냥 배열로 모두 만들어준 뒤에 순차적으로 도는 것도 나쁘지 않다

 

코드

#include <iostream>
using namespace std;
int N, M;
int p[501][501];
int ans = 0;
bool check(int x, int y)
{

    if (x >= 0 && x < N && y >= 0 && y < M)
    {
        return true;
    }

    else
    {
        return false;
    }
}

void one(int x, int y, int dir)
{
    bool result = true;
    int sum = 0;
    for (int j = 0; j < 4; j++)
    {

        int nx = (dir == 1 ? x : x + j);
        int ny = (dir == 1 ? y + j : y);

        if (check(nx, ny))
        {
            sum += p[nx][ny];
        }
        else
        {

            result = false;
            break;
        }
    }
    if (result)
    {

        ans = max(ans, sum);
    }
}

void two(int x, int y)
{
    bool result = true;
    int sum = 0;

    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            if (check(x + i, y + j))
            {
                sum += p[x + i][y + j];
            }
            else
            {
                result = false;
                break;
            }
        }
    }

    if (result)
    {
        ans = max(ans, sum);
    }
}

void three(int x, int y, int dir)
{

    int dy[] = {0, -1, 1, 0};
    int dx[] = {0, 0, 0, 1};
    int dx_anti[] = {0, 0, 0, -1};

    bool result = true;
    int sum = 0;

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

        int nx = dir == 1 ? (x + dx[i]) : (x + dy[i]);
        int ny = dir == 1 ? (y + dy[i]) : (y + dx[i]);
        if (check(nx, ny))
        {
            sum += p[nx][ny];
        }
        else
        {
            result = false;
            break;
        }
    }

    if (result)
    {
        ans = max(ans, sum);
    }
    result = true;
    sum = 0;

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

        int nx = dir == 1 ? (x + dx_anti[i]) : (x + dy[i]);
        int ny = dir == 1 ? (y + dy[i]) : (y + dx_anti[i]);
        if (check(nx, ny))
        {
            sum += p[nx][ny];
        }
        else
        {
            result = false;
            break;
        }
    }

    if (result)
    {
        ans = max(ans, sum);
    }
}

void four(int x, int y, int dir)
{

    int dx[] = {0, 0, 1, 1};
    int dy[] = {0, -1, 0, 1};

    bool result = true;
    int sum = 0;

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

        int nx = dir == 1 ? (x + dx[i]) : (x + dy[i]);
        int ny = dir == 1 ? (y + dy[i]) : (y + dx[i]);
        if (check(nx, ny))
        {
            sum += p[nx][ny];
        }
        else
        {
            result = false;
            break;
        }
    }

    if (result)
    {
        ans = max(ans, sum);
    }

    result = true;
    sum = 0;
    int dx_anti[] = {0, -1, 1, 0};
    int dy_anti[] = {0, 1, 0, 1};

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

        int nx = dir == 1 ? (x + dx_anti[i]) : (x + dy_anti[i]);
        int ny = dir == 1 ? (y + dy_anti[i]) : (y + dx_anti[i]);
        if (check(nx, ny))
        {
            sum += p[nx][ny];
        }
        else
        {
            result = false;
            break;
        }
    }

    if (result)
    {
        ans = max(ans, sum);
    }
}

void five(int x, int y, int dir)
{

    int dx[] = {0, 0, 1, 2};
    int dy[] = {0, 1, 1, 1};

    bool result = true;
    int sum = 0;

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

        int nx = dir == 1 ? (x + dx[i]) : (x + dy[i]);
        int ny = dir == 1 ? (y + dy[i]) : (y + dx[i]);
        if (check(nx, ny))
        {
            sum += p[nx][ny];
        }
        else
        {
            result = false;
            break;
        }
    }

    if (result)
    {
        ans = max(ans, sum);
    }

    int dx_1[] = {0, 0, 1, 2};
    int dy_1[] = {0, -1, -1, -1};

    result = true;
    sum = 0;

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

        int nx = dir == 1 ? (x + dx_1[i]) : (x + dy_1[i]);
        int ny = dir == 1 ? (y + dy_1[i]) : (y + dx_1[i]);
        if (check(nx, ny))
        {
            sum += p[nx][ny];
        }
        else
        {
            result = false;
            break;
        }
    }

    if (result)
    {
        ans = max(ans, sum);
    }

    int dx_2[] = {0, 0, -1, -2};
    int dy_2[] = {0, 1, 1, 1};

    result = true;
    sum = 0;

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

        int nx = dir == 1 ? (x + dx_2[i]) : (x + dy_2[i]);
        int ny = dir == 1 ? (y + dy_2[i]) : (y + dx_2[i]);
        if (check(nx, ny))
        {
            sum += p[nx][ny];
        }
        else
        {
            result = false;
            break;
        }
    }

    if (result)
    {
        ans = max(ans, sum);
    }

    int dx_3[] = {0, 0, -1, -2};
    int dy_3[] = {0, -1, -1, -1};

    result = true;
    sum = 0;

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

        int nx = dir == 1 ? (x + dx_3[i]) : (x + dy_3[i]);
        int ny = dir == 1 ? (y + dy_3[i]) : (y + dx_3[i]);
        if (check(nx, ny))
        {
            sum += p[nx][ny];
        }
        else
        {
            result = false;
            break;
        }
    }

    if (result)
    {
        ans = max(ans, sum);
    }
}

int main(void)
{

    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> p[i][j];
        }
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {

            one(i, j, 0); //1번 모양
            one(i, j, 1);

            two(i, j); //2번 모양

            three(i, j, 0); //3번 모양
            three(i, j, 1);

            four(i, j, 0); //4번 모양
            four(i, j, 1);

            five(i, j, 0); //5번 모양
            five(i, j, 1);
        }
    }
    cout << ans << '\n';

    return 0;
}

더 좋은 코드는 해당 블로그를 참고 하자

rebas.kr/792