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

문제

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

14500번: 테트로미노

 

설명

 

엄청난 노가다 문제다. 위 4개의 테트로미노 모양으로 숫자를 묶었을 때 가장 큰 수를 출력해야 하는데, 문제는 테트로미노를 회전하고 대칭시켜도 된다는 것이다. 그래서 총 2(하늘) + 1(노랑) + 4(분홍) + 4(초록) + 8(주황) = 19개의 경우의 수가 있는데 이걸 하나하나 계산하고 싶지는 않았다. 그래서 짱돌같은 내 머리를 열심히 굴려 좀 더 예쁜 코드를 짰다. 

 

하늘색 경우의 수 2개 중 1가지, 분홍색 경우의 수 4개 중 2가지, 주황색 경우의 수 8개 중 4가지 이렇게 총 8개는 가로로 긴 블록 3개의 위, 아래, 양 옆에 블록을 하나씩 붙여 만든 블록이다. 이렇게 하면 하나의 반복문을 통해 총 7가지 경우의 수를 커버할 수 있다. (가로 긴 4개 블록은 중복인데, 중복이 있어도 답 내는 데엔 문제 없다.) 세로로 긴 블록의 양옆, 위, 아래에 이런 식으로 블록을 붙여나갈 수 있는데, 이 때에도 총 7가지 경우의 수를 커버할 수 있다. 여기까지 반복문 2개로 14가지 경우의 수를 커버할 수 있다.

나머지 노란색과 초록색 테트로미노는 블록 2개를 베이스로 요리조리 어떻게 하면 또 묶어볼 수 있을 것 같았는데, 그냥 노가다로 짜도 될 것 같아서 그렇게 했따.

 

문제는 도형 모양이 조금 더럽기 때문에, 주어진 숫자 배열을 모두 체크하려면 테트로미노마다 배열을 벗어나는 경우에 예외처리를 힘들게 해줘야 할 것 같았다. 그러긴 싫어서 그냥 초기 배열 크기를 넉넉하게 잡고 0으로 채워준 다음, [2][2] 위치부터 숫자를 입력받아서 크기 2짜리 패딩을 줬다. 이렇게 첫칸부터 끝칸까지 런타임 에러 없이 마음껏 탐색하도록 했다.

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[]) {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    
    int N, M;
    int arr[510][510] = {0};
    int answer = 0;
    
    cin >> N >> M;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i+2][j+2];
        }
    }
    for (int i = 2; i < N + 2; i++) {
        for (int j = 2; j < M + 2; j++) {
            // 세로로 길게 3개
            int di[] = {-1, 0, 1, 2, 3, 2, 1, 0};
            int dj[] = {0, 1, 1, 1, 0, -1, -1, -1};
            int tmp = arr[i][j] + arr[i+1][j] + arr[i+2][j];
            for (int k = 0; k < 8; k++) {
                int tmp2 = tmp + arr[i + di[k]][j + dj[k]];
                answer = max(tmp2, answer);
            }
            // 가로로 길게 3개
            int tmp_2 = arr[i][j] + arr[i][j+1] + arr[i][j+2];
            for (int k = 0; k < 8; k++) {
                int tmp2_2 = tmp_2 + arr[i + dj[k]][j + di[k]];
                answer = max(tmp2_2, answer);
            }
            // 노랑
            int tmp_3 = arr[i][j] + arr[i][j+1] + arr[i+1][j] + arr[i+1][j+1];
            answer = max(tmp_3, answer);
            // 초록 1
            int tmp_4 = arr[i][j] + arr[i][j+1] + arr[i-1][j+1] + arr[i-1][j+2];
            answer = max(tmp_4, answer);
            // 초록 2
            int tmp_5 = arr[i][j] + arr[i][j+1] + arr[i+1][j+1] + arr[i+1][j+2];
            answer = max(tmp_5, answer);
            // 초록 3
            int tmp_6 = arr[i][j] + arr[i+1][j] + arr[i+1][j+1] + arr[i+2][j+1];
            answer = max(tmp_6, answer);
            // 초록 4
            int tmp_7 = arr[i][j] + arr[i+1][j] + arr[i+1][j-1] + arr[i+2][j-1];
            answer = max(tmp_7, answer);
        }
    }
    
    cout << answer;
    return 0;
}