우주의 IT 소행성

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
score_board = [list(map(int, input().split())) for _ in range(n)]

tetrominos = [
    [(0, 1), (0, 2), (0, 3)],  # 가로 막대기
    [(1, 0), (2, 0), (3, 0)],  # 세로 막대기
    [(0, 1), (1, 0), (1, 1)],  # 네모
    [(1, 0), (2, 0), (2, 1)],  # 긴 ㄴ
    [(1, 0), (2, 0), (2, -1)],  # 긴 ㄴ 대칭 / 5
    [(0, 1), (0, 2), (1, 2)],  # ㄱ
    [(0, 1), (0, 2), (1, 0)],  # ㄱ 대칭
    [(0, 1), (1, 1), (2, 1)],  # 긴 ㄱ
    [(0, 1), (1, 0), (2, 0)],  # 긴 ㄱ 대칭
    [(0, 1), (0, 2), (-1, 2)],  # ㄴ 대칭 / 10
    [(1, 0), (1, 1), (1, 2)],  # ㄴ
    [(1, 0), (1, 1), (2, 1)],  # 선 ㄹ
    [(1, 0), (1, -1), (2, -1)],  # 선 ㄹ 대칭
    [(0, 1), (1, 0), (1, -1)],  # ㄹ 대칭
    [(0, 1), (1, 1), (1, 2)],  # ㄹ / 15
    [(0, 1), (0, 2), (1, 1)],  # ㅜ
    [(0, 1), (0, 2), (-1, 1)],  # ㅗ
    [(1, 0), (2, 0), (1, -1)],  # ㅓ
    [(1, 0), (2, 0), (1, 1)],  # ㅏ / 19
]

result = 0
for i in range(n):
    for j in range(m):
        for tetromino in tetrominos:
            flag = True
            score = score_board[i][j]
            for nx, ny in tetromino:
                x, y = nx + i, ny + j
                if 0 <= x < n and 0 <= y < m:
                    score += score_board[x][y]
                else:
                    flag = False
                    break
            if flag:
                if score > result:
                    result = score
print(result)

14500 테트로미노 풀이방법

일단 N * M 종이 위에 모든 종류의 테트로미노를 전부 놔 본다고 생각해보자.

일단 테트로미노의 종류를 구해야 할 것이다.

테트로미노는 회전과 대칭이 가능하므로

그림을 그려보면 다음과 같이 19종류의 테트로미노가 나온다.

각 테트로미노별로 N*M 배열에서 놓을 수 있는 경우의 수를 구해 시간복잡도를 구해보면

19 * O(3NM) 정도가 되는데, 결국 상수항은 제하고 O(NM)이 된다.

i, j = 0, 0

도형의 좌측 상단을 기준점으로 잡고 각 회전/대칭 도형의 칸별 좌표를 입력해주고

19번의 반복문 속에서 미리 입력된 회전/대칭 도형들을 끼워맞춘다.

맞출 때 마다 해당 칸의 수들의 최대값을 비교하여 작으면 해당 칸을 최대 값으로 갱신한다.