[BOJ] #14500 테트로미노

시간 제한	메모리 제한	정답 비율
2 초	512 MB	32.965%

 

14500번: 테트로미노

 

해결방법

기존 테트로미노에서 회전과 대칭된 모양까지 고려해야 했는데, 회전만 고려해서 문제를 풀었기 때문에 한 번 틀렸었다.

다음의 테스트케이스에서 출력은 10이 되어야 한다.

4 4
0 0 0 0
0 0 0 1
0 0 0 2
0 0 4 3

 

문제에서 주어진 테트로미노를 가지고 회전했을 때, 대칭했을 때 모양을 모두 고려한 인덱스의 이동을 이차원 배열에 모두 저장해 두고 한 행에 대해서 순회를 할 때 4개씩 끊어 합계를 구해 MAX값을 갱신하였다.

 

 

메모리	시간
2984 KB	56 ms

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int, int> p;
int n, m, arr[505][505], ans;
vector<vector<p>> tetromino = { {{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},{0,2},{1,0},{0,0},{0,-1},{1,0},{2,0},{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},{0,1},{0,2},{1,2}},
                                {{0,0}, {1,0}, {1,1}, {2,1}, {0,0}, {0,1}, {1,-1}, {1,0},{0,0},{1,0},{1,-1},{2,-1},{0,0},{0,1},{1,1},{1,2}},
                                {{0,0},{0,1},{0,2},{1,1},{0,0},{1,0},{2,0},{1,-1},{0,0},{1,0},{1,-1},{1,1},{0,0},{1,0},{2,0},{1,1}} };
void go(int r, int c) {
    for (int i = 0; i < 5; i++) {
        int sum = 0;
        for (int j = 0; j < tetromino[i].size(); j++) {
            if (!(j % 4)) {
                ans = max(ans, sum); sum = 0;
            }
            p next = tetromino[i][j];
            int nr = r + next.first; int nc = c + next.second;
            if (nr >= 0 && nr < n && nc >= 0 && nc < m) sum += arr[nr][nc];
        }
        ans = max(ans, sum);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            go(i, j);
        }
    }
    printf("%d", ans);
    return 0;
}