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

 📚 문제

[BOJ C++] 백준 14500번: 테트로미노
https://www.acmicpc.net/problem/14500

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• 가능한 모든 경우의 수를 모두 구현하면 해결할 수 있는 문제이다. 말은 쉽지만 모든 경우의 수를 고려하는 것이 은근 어렵다... 😥
• 필자는 반복문의 범위를 고려하기 위해 테트로미노 조각의 크기를 직사각형으로 생각하여 케이스를 나누어 구현하였다. 반복문이 배열의 범위를 넘어가지 않도록 주의하자!
• 테트로미노 조각의 전체 종류는 다음과 같다.

 1) 가로4 * 세로1, 가로1 * 세로4, 가로2 * 세로2

 

 2) 가로2 * 세로3

 

 3) 가로3 * 세로2

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, mx = 0;
    cin >> n >> m;
    vector<vector<int>> v(n, vector<int>(m));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> v[i][j];

    for (int i = 0; i < n; i++)  // 가로4 * 세로1.
        for (int j = 0; j < m - 3; j++) mx = max(mx, v[i][j] + v[i][j + 1] + v[i][j + 2] + v[i][j + 3]);

    for (int i = 0; i < n - 3; i++)  // 가로1 * 세로4.
        for (int j = 0; j < m; j++) mx = max(mx, v[i][j] + v[i + 1][j] + v[i + 2][j] + v[i + 3][j]);

    for (int i = 0; i < n - 1; i++)  // 정사각형. 가로2 * 세로2.
        for (int j = 0; j < m - 1; j++) mx = max(mx, v[i][j] + v[i][j + 1] + v[i + 1][j] + v[i + 1][j + 1]);

    for (int i = 0; i < n - 2; i++) {  // 가로2 * 세로3.
        for (int j = 0; j < m - 1; j++) {
            mx = max(mx, v[i][j] + v[i + 1][j] + v[i + 2][j] + v[i][j + 1]);
            mx = max(mx, v[i][j] + v[i + 1][j] + v[i + 2][j] + v[i + 1][j + 1]);
            mx = max(mx, v[i][j] + v[i + 1][j] + v[i + 2][j] + v[i + 2][j + 1]);
            mx = max(mx, v[i][j + 1] + v[i + 1][j + 1] + v[i + 2][j + 1] + v[i][j]);
            mx = max(mx, v[i][j + 1] + v[i + 1][j + 1] + v[i + 2][j + 1] + v[i + 1][j]);
            mx = max(mx, v[i][j + 1] + v[i + 1][j + 1] + v[i + 2][j + 1] + v[i + 2][j]);
            mx = max(mx, v[i][j] + v[i + 1][j] + v[i + 1][j + 1] + v[i + 2][j + 1]);
            mx = max(mx, v[i][j + 1] + v[i + 1][j] + v[i + 1][j + 1] + v[i + 2][j]);
        }
    }

    for (int i = 0; i < n - 1; i++) {  // 가로3 * 세로2.
        for (int j = 0; j < m - 2; j++) {
            mx = max(mx, v[i][j] + v[i][j + 1] + v[i][j + 2] + v[i + 1][j]);
            mx = max(mx, v[i][j] + v[i][j + 1] + v[i][j + 2] + v[i + 1][j + 1]);
            mx = max(mx, v[i][j] + v[i][j + 1] + v[i][j + 2] + v[i + 1][j + 2]);
            mx = max(mx, v[i + 1][j] + v[i + 1][j + 1] + v[i + 1][j + 2] + v[i][j]);
            mx = max(mx, v[i + 1][j] + v[i + 1][j + 1] + v[i + 1][j + 2] + v[i][j + 1]);
            mx = max(mx, v[i + 1][j] + v[i + 1][j + 1] + v[i + 1][j + 2] + v[i][j + 2]);
            mx = max(mx, v[i][j] + v[i][j + 1] + v[i + 1][j + 1] + v[i + 1][j + 2]);
            mx = max(mx, v[i][j + 1] + v[i][j + 2] + v[i + 1][j + 1] + v[i + 1][j]);
        }
    }
    cout << mx;
}