백준[14500] 테트로미노

삼성 SW역량테스트 문제이다.

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

5개 모양의 블럭중 하나를 적절히 놓아 2차원 배열의 칸에 쓰인 수의 최대합을 구하는 문제이다.

이 문제는 회전,대칭에서 5개모양의 블럭이 총 19개의 모양을 가질수 있음을 알고 접근하면 된다.

필자는 이 19개 모양을 모두 탐색하는 방법을 사용하였으며, 한 좌표에서 그 모양이 가능한지를 확인하고 가능하면 최대값들을 갱신시켰다.

그리고 확인한 19개의 모양을 토대로 최대값을 출력하였다.

*코드가 깔끔하지 않고 전형적인 탐색방법을 사용해서 구현이 복잡하다, 이것이 최적의 답이 아니고 다른 방법도 존재한다.*

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<stack>
 
using namespace std;
 
int arr[510][510];
 
int main()
{
    int n, m, ans[19] = { 0 }, a = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j <= m && j + 3 <= m) // ㅡ
                ans[0] = max(arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i][j + 3], ans[0]);
 
            if (i <= n && i + 3 <= n)// ㅣ
                ans[1] = max(arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 3][j], ans[1]);

 
            if ((i <= n && j <= m) && (i + 1 <= n && j <= m) && (i <= n && j + 1 <= m) && (i + 1 <= n && j + 1 <= m)) // ㅁ모양
                ans[2] = max(arr[i][j] + arr[i + 1][j] + arr[i][j + 1] + arr[i + 1][j + 1], ans[2]);
 


            if ((i <= n && j <= m) && (i + 1 <= n && j <= m) && (i + 1 <= n && j + 1 <= m) && (i + 2 <= n && j + 1 <= m))  //ㄱㄴ 모양
                ans[3] = max(arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 2][j + 1], ans[3]);
 
            if ((i + 1 <= n && j <= m) && (i + 1 <= n && j + 1 <= m) && (i <= n && j + 1 <= m) && (i <= n && j + 2 <= m))
                ans[4] = max(arr[i + 1][j] + arr[i + 1][j + 1] + arr[i][j + 1] + arr[i][j + 2], ans[4]);
 
            if ((i + 1 <= n && j <= m) && (i + 2 <= n && j <= m) && (i + 1 <= n && j + 1 <= m) && (i <= n && j + 1 <= m))
                ans[5] = max(arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j + 1] + arr[i][j + 1], ans[5]);
 
            if ((i <= n && j <= m) && (i <= n && j + 1 <= m) && (i + 1 <= n && j + 1 <= m) && (i + 1 <= n && j + 2 <= m))
                ans[6] = max(arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 1][j + 2], ans[6]);
 


            if ((i <= n && j <= m) && (i <= n && j + 2 <= m) && (i + 1 <= n && j + 1 <= m) && (i <= n && j + 1 <= m)) //ㅜ
                ans[7] = max(arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 1], ans[7]);
 
            if ((i + 1 <= n && j <= m) && (i <= n && j + 1 <= m) && (i + 2 <= n && j + 1 <= m) && (i + 1 <= n && j + 1 <= m)) // ㅓ
                ans[8] = max(arr[i + 1][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 2][j + 1], ans[8]);
 
            if ((i + 1 <= n && j <= m) && (i <= n && j + 1 <= m) && (i + 1 <= n && j + 2 <= m) && (i + 1 <= n && j + 1 <= m)) // ㅗ
                ans[9] = max(arr[i + 1][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 1][j + 2], ans[9]);
 
            if ((i <= n && j <= m) && (i + 2 <= n && j <= m) && (i + 1 <= n && j + 1 <= m) && (i + 1 <= n && j <= m)) // ㅏ
                ans[10] = max(arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j + 1], ans[10]);
 

            if ((i <= n && j <= m) && (i + 2 <= n && j <= m) && (i + 2 <= n && j + 1 <= m) && (i + 1 <= n && j <= m)) // ㄴ 모양 8가지
                ans[11] = max(arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 2][j + 1], ans[11]);
 

            if ((i <= n && j <= m) && (i + 1 <= n && j <= m) && (i <= n && j + 2 <= m) && (i <= n && j + 1 <= m))
                ans[12] = max(arr[i][j] + arr[i + 1][j] + arr[i][j + 1] + arr[i][j + 2], ans[12]);
 

            if ((i <= n && j <= m) && (i <= n && j + 1 <= m) && (i + 2 <= n && j + 1 <= m) && (i + 1 <= n && j + 1 <= m))
                ans[13] = max(arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 2][j + 1], ans[13]);
 

            if ((i + 1 <= n && j <= m) && (i + 1 <= n && j + 2 <= m) && (i <= n && j + 2 <= m) && (i + 1 <= n && j + 1 <= m))
                ans[14] = max(arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 1][j + 2] + arr[i][j + 2], ans[14]);
 

            if ((i + 2 <= n && j <= m) && (i + 2 <= n && j + 1 <= m) && (i <= n && j + 1 <= m) && (i + 1 <= n && j + 1 <= m))
                ans[15] = max(arr[i + 2][j] + arr[i + 2][j + 1] + arr[i + 1][j + 1] + arr[i][j + 1], ans[15]);
 

            if ((i <= n && j <= m) && (i + 1 <= n && j <= m) && (i + 1 <= n && j + 2 <= m) && (i + 1 <= n && j + 1 <= m))
                ans[16] = max(arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 1][j + 2], ans[16]);
 

            if ((i <= n && j <= m) && (i + 2 <= n && j <= m) && (i <= n && j + 1 <= m) && (i + 1 <= n && j <= m))
                ans[17] = max(arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 2][j], ans[17]);
 

            if ((i <= n && j <= m) && (i <= n && j + 2 <= m) && (i + 1 <= n && j + 2 <= m) && (i <= n && j + 1 <= m))
                ans[18] = max(arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 2], ans[18]);
        }
    }
    for (int i = 0; i < 19; i++) a = max(ans[i], a);
    cout << a;
    return 0;
}