[BOJ / Python] 14500번 : 테트로미노

문제 제목, 난이도

14500번 : 테트로미노, 골드5

---

문제 링크

www.acmicpc.net/problem/14500

14500번: 테트로미노

---

코드(Python)

import sys
sys.setrecursionlimit(100)

input = sys.stdin.readline

n, m = map(int,input().split())

li = []

for _ in range(n) :
    li.append(list(map(int,input().split())))

ali = [[0,1],[0,1],[0,1],[0,1],[0,1],[0,1],[0,1],[0,1],[1,0],[1,0],[1,0],[1,0],[1,0],[1,0],[1,0],[1,0],[1,0],[0,1],[0,1]]
bli = [[0,2],[0,2],[0,2],[0,2],[0,2],[0,2],[0,2],[1,0],[2,0],[2,0],[2,0],[2,0],[2,0],[2,0],[2,0],[1,1],[1,-1],[1,1],[1,0]]
cli = [[0,3],[1,2],[1,1],[1,0],[-1,0],[-1,1],[-1,2],[1,1],[0,1],[1,1],[2,1],[2,-1],[1,-1],[0,-1],[3,0],[2,1],[2,-1],[1,2],[1,-1]]

ans = 0
def fun(x, y) :
    for _ in range(19) :
        global ans
        p1 = [x+ali[_][0],y+ali[_][1]]
        p2 = [x+bli[_][0],y+bli[_][1]]
        p3 = [x+cli[_][0],y+cli[_][1]]

        if p1[0] < 0 or p2[0] < 0 or p3[0] < 0 or p1[0] >= n or p2[0] >= n or p3[0] >= n or p1[1] < 0 or p2[1] < 0 or p3[1] < 0 or p1[1] >= m or p2[1] >= m or p3[1] >= m :
            continue
        
        tmp = li[x][y]+li[p1[0]][p1[1]]+li[p2[0]][p2[1]]+li[p3[0]][p3[1]]
        if ans <= tmp :
            ans = tmp
        

for i in range(n) :
    for j in range(m) :
        fun(i, j)

print(ans)
    

---

풀이

i,j 를 p0 로 하는 테트로미노를 p1, p2, p3을 설정하면서 최대값을 확인하는 과정

---

체크리스트

완전탐색(브루트포스)

테트로미노의 경우의 수는 19가지이고 4 <= N,M <= 500 이므로 브루트포스를 이용한 시간복잡도는 500 * 500 * 19 로 제한시간 2초보다 작기때문에 이를 이용하는 풀이가 가능하다.