백준 14500 테트로미노 (C++)

안유태·2022년 8월 11일
0

알고리즘

목록 보기
20/239

14500번: 테트로미노

완전 탐색을 이용한 구현 문제이다. 문제를 보면 총 5가지 종류의 테트로미노가 존재하는데 거기다가 회전과 대칭까지 존재한다. 구현 자체는 어렵지 않지만 굉장히 귀찮은 문제였다. 다른 분들이 푼 것을 보니 DFS를 이용하여 문제를 푼 분들도 있던데 나는 간단히 반복문 노가다(?)를 통해 풀었다.



#include <iostream>
#include <algorithm>

using namespace std;

int N, M, res = 0, tmp;
int A[501][501];

void case1() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M - 3; j++) {
            tmp = A[i][j] + A[i][j + 1] + A[i][j + 2] + A[i][j + 3];
            res = max(res, tmp);
        }
    }

    for (int i = 0; i < N - 3; i++) {
        for (int j = 0; j < M; j++) {
            tmp = A[i][j] + A[i + 1][j] + A[i + 2][j] + A[i + 3][j];
            res = max(res, tmp);
        }
    }
}

void case2() {
    for (int i = 0; i < N - 1; i++) {
        for (int j = 0; j < M - 1; j++) {
            tmp = A[i][j] + A[i][j + 1] + A[i + 1][j] + A[i + 1][j + 1];
            res = max(res, tmp);
        }
    }
}

void case3() {
    for (int i = 0; i < N - 2; i++) {
        for (int j = 0; j < M - 1; j++) {
            tmp = A[i][j] + A[i + 1][j] + A[i + 2][j] + A[i + 2][j + 1];
            res = max(res, tmp);

            tmp = A[i][j] + A[i + 1][j] + A[i + 2][j] + A[i][j + 1];
            res = max(res, tmp);

            tmp = A[i][j] + A[i][j + 1] + A[i + 1][j + 1] + A[i + 2][j + 1];
            res = max(res, tmp);

            tmp = A[i + 2][j] + A[i][j + 1] + A[i + 1][j + 1] + A[i + 2][j + 1];
            res = max(res, tmp);
        }
    }

    for (int i = 0; i < N - 1; i++) {
        for (int j = 0; j < M - 2; j++) {
            tmp = A[i][j] + A[i][j + 1] + A[i][j + 2] + A[i + 1][j];
            res = max(res, tmp);

            tmp = A[i][j] + A[i][j + 1] + A[i][j + 2] + A[i + 1][j + 2];
            res = max(res, tmp);

            tmp = A[i][j] + A[i + 1][j] + A[i + 1][j + 1] + A[i + 1][j + 2];
            res = max(res, tmp);

            tmp = A[i][j+2] + A[i + 1][j] + A[i + 1][j + 1] + A[i + 1][j + 2];
            res = max(res, tmp);
        }
    }
}

void case4() {
    for (int i = 0; i < N - 2; i++) {
        for (int j = 0; j < M - 1; j++) {
            tmp = A[i][j] + A[i + 1][j] + A[i + 1][j + 1] + A[i + 2][j + 1];
            res = max(res, tmp);

            tmp = A[i][j + 1] + A[i + 1][j + 1] + A[i + 1][j] + A[i + 2][j];
            res = max(res, tmp);
        }
    }

    for (int i = 0; i < N - 1; i++) {
        for (int j = 0; j < M - 2; j++) {
            tmp = A[i + 1][j] + A[i + 1][j + 1] + A[i][j + 1] + A[i][j + 2];
            res = max(res, tmp);

            tmp = A[i][j] + A[i][j + 1] + A[i + 1][j + 1] + A[i + 1][j + 2];
            res = max(res, tmp);
        }
    }
}

void case5() {
    for (int i = 0; i < N - 1; i++) {
        for (int j = 0; j < M - 2; j++) {
            tmp = A[i][j] + A[i][j + 1] + A[i][j + 2] + A[i + 1][j + 1];
            res = max(res, tmp);

            tmp = A[i][j + 1] + A[i + 1][j] + A[i + 1][j + 1] + A[i + 1][j + 2];
            res = max(res, tmp);
        }
    }

    for (int i = 0; i < N - 2; i++) {
        for (int j = 0; j < M - 1; j++) {
            tmp = A[i][j] + A[i + 1][j] + A[i + 2][j] + A[i + 1][j + 1];
            res = max(res, tmp);

            tmp = A[i + 1][j] + A[i][j + 1] + A[i + 1][j + 1] + A[i + 2][j + 1];
            res = max(res, tmp);
        }
    }
}

void solution() {
    case1();
    case2();
    case3();
    case4();
    case5();

    cout << res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;

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

    solution();

    return 0;
}
profile
공부하는 개발자

0개의 댓글