[삼성 SW 역량 기출] 백준 14500 (C++) 테트로미노

 

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

14500번: 테트로미노

 

 

브루트포스로 해결한다 하더라도 시간복잡도는 O(NM)이다.

가능한 모양의 개수 19개를 N*M개만큼 적용하는 것이다!

그러므로 맘 편하게 브루트포스로 해결했다.

 

다른 풀이를 찾아보니 depth를 5로 정하여 탐색하는 방법도 있는 듯하다.

 

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <deque>
using namespace std;
// O(NM)
const int MAX = 500;
int n, m;
int board[MAX][MAX];

pair<int, int> Tet[][4] = {
    {{0, 0}, {0, 1}, {0, 2}, {0, 3}},
    {{0, 0}, {1, 0}, {2, 0}, {3, 0}},
    
    {{0, 0}, {0, 1}, {1, 0}, {1, 1}},
    
    {{0, 0}, {1, 0}, {2, 0}, {2, 1}},
    {{0, 0}, {0, 1}, {1, 1}, {2, 1}},
    {{0, 0}, {0, 1}, {0, 2}, {-1, 2}},
    {{0, 0}, {1, 0}, {0, 1}, {0, 2}},
    {{0, 0}, {0, 1}, {0, 2}, {1, 2}},
    {{0, 0}, {1, 0}, {2, 0}, {2, -1}},
    {{0, 0}, {1, 0}, {1, 1}, {1, 2}},
    {{0, 0}, {1, 0}, {2, 0}, {0, 1}},
    
    {{0, 0}, {1, 0}, {1, 1}, {2, 1}},
    {{0, 0}, {1, 0}, {0, 1}, {-1, 1}},
    {{0, 0}, {0, 1}, {1, 1}, {1, 2}},
    {{0, 0}, {0, 1}, {-1, 1}, {-1, 2}},

    {{0, 0}, {0, 1}, {0, 2}, {1, 1}},
    {{0, 0}, {0, 1}, {1, 1}, {-1, 1}},
    {{0, 0}, {0, 1}, {0, 2}, {-1, 1}},
    {{0, 0}, {1, 0}, {2, 0}, {1, 1}},
};

void sol() {
    int sum = 0, ans = 0;
    for (int i = 0; i < 19; i++) {
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                sum = 0;
                for (auto cur : Tet[i]) {
                    int nx = x + cur.first;
                    int ny = y + cur.second;
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                        sum = 0;
                        break;
                    }
                    sum += board[nx][ny];
                }
                ans = max(ans, sum);
            }
        }
    }
    cout << ans;
}

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 >> board[i][j];
        }
    }
    sol();

    return 0;
}

 

반례

 

https://www.acmicpc.net/board/view/61597

글 읽기 - 14500 테크노마트 좋은 반례 공유(끌올)합니다.