[BOJ/백준 14500][C++] 테트로미노

문제

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

백준 14500

 

문제 내용

위의 도형 5가지는 회전시키거나 뒤집을 수 있다.

각 칸에 정수가 적힌 배열을 입력받고, 그 배열에 위 도형 중 하나를 올려놓는다.

올려진 부분의 정수를 모두 더한 값이 최대가 되도록 하면 된다.

 

문제 풀이

브루트포스로 문제를 해결할 수 있다.

도형이 차지할 수 있는 범위를 모두 적어두고, 반복문을 전부 돌려보면 된다.

 

코드

#include <iostream>
#include <vector>

using namespace std;
int n, m;
int arr[500][500];

vector<vector<vector<bool>>> puzzle = {{{true, true, true, true}},
                                       {{true}, {true}, {true}, {true}},

                                       {{true, true}, {true, true}},

                                       {{true, true, true}, {true, false, false}},
                                       {{false, false, true}, {true, true, true}},
                                       {{true, true}, {false, true}, {false, true}},
                                       {{true, false}, {true, false}, {true, true}},
                                       {{true, false, false}, {true, true, true}},
                                       {{true, true}, {true, false}, {true, false}},
                                       {{false, true}, {false, true}, {true, true}},
                                       {{true, true, true}, {false, false, true}},

                                       {{true, false}, {true, true}, {false, true}},
                                       {{false, true, true}, {true, true, false}},
                                       {{false, true}, {true, true}, {true, false}},
                                       {{true, true, false}, {false, true, true}},

                                       {{true, true, true}, {false, true, false}},
                                       {{false, true, false}, {true, true, true}},
                                       {{true, false}, {true, true}, {true, false}},
                                       {{false, true}, {true, true}, {false, true}}};

int calcSumOfPuzzle(vector<vector<bool>> &puzzle, int r, int c) {
    int ssum = 0;
    for (int i = 0; i < puzzle.size(); i++) {
        for (int j = 0; j < puzzle[0].size(); j++) {
            if (puzzle[i][j]) {
                ssum += arr[r + i][c + j];
            }
        }
    }
    return ssum;
}

int solution() {
    int mmax = -1;
    for (int i = 0; i < puzzle.size(); i++) {
        int rowSize = puzzle[i].size();
        int colSize = puzzle[i][0].size();

        for (int j = 0; j <= n - rowSize; j++) {
            for (int k = 0; k <= m - colSize; k++) {
                mmax = max(mmax, calcSumOfPuzzle(puzzle[i], j, k));
            }
        }
    }
    return mmax;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }

    cout << solution();
}