백준 14500번 테트로미노

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

14500번: 테트로미노

생성해야 하는 Matrix의 범위가 <=500으로 매우 작은 경우의 수를 가지고 문제를 읽다 보니 뭔가 그냥 브루트 포스로 풀어야 할 것 같아서 브루트 포스로 풀었다.

 

생성 가능한 폴리오미노를 전부 노가다로... 미리 정의해두고 Matrix의 크기만큼 순회를 하여 최대값을 찾는 방법으로 풀었으며 다행히 python3로도 제출해도 TLE는 나오지 않았다.

 

import sys
input = sys.stdin.readline

a,b = map(int,input().split())
matrix = []
for _ in range(a):
    matrix.append(list(map(int,input().split())))

# 생성가능한 폴리오미노 사전 정의
polyomino = [[[0,0],[0,1],[1,0],[1,1]],
[[0,0],[0,1],[0,2],[0,3]],
[[0,0],[1,0],[2,0],[3,0]],
[[0,0],[1,0],[2,0],[2,1]],
[[0,1],[1,1],[2,1],[2,0]],
[[0,0],[0,1],[1,1],[2,1]],
[[0,0],[0,1],[1,0],[2,0]],
[[0,0],[1,0],[1,1],[2,1]],
[[0,1],[1,1],[1,0],[2,0]],
[[1,0],[1,1],[0,1],[0,2]],
[[0,0],[0,1],[1,1],[1,2]],
[[0,0],[0,1],[0,2],[1,1]],
[[0,1],[1,0],[1,1],[1,2]],
[[1,0],[1,1],[0,1],[2,1]],
[[0,0],[1,0],[2,0],[1,1]],
[[0,0],[1,0],[1,1],[1,2]],
[[1,0],[1,1],[1,2],[0,2]],
[[0,0],[0,1],[0,2],[1,0]],
[[0,0],[0,1],[0,2],[1,2]]
]

result = -1
# Matrix의 크기 만큼 인덱스를 순회 i => x축, j => y축
for i in range(a):
    for j in range(b):

        for each in polyomino:
            tmp_sum = 0
            flag = 0
            # 생성가능한 테트로미노를 순회하면서 임시로 합계값을 계산
            for k in each:
                x = k[0] + i
                y = k[1] + j
                if 0 <= x < a and 0 <= y < b:
                    tmp_sum += matrix[x][y]
                else:
                    # 4개로 구성된 테트로미노 중 하나라도 Matrix의 범위를 벗어나면 flag = 1
                    flag = 1

            if flag:
                continue
            else:
                # 이전에 찾은 합계값보다 작으면 결과값 갱신
                if tmp_sum > result:
                    result = tmp_sum

print(result)