[BOJ] 14500: 테트로미노(Python)

14500번: 테트로미노

문제 설명

정사각형 4개를 이어 붙인 도형을 테트로미노라고 한다. n*m 크기의 종이 위에 숫자가 쓰여 있다. 테트로미노 1개를 종이에 올려 덮어진 칸의 합이 가장 크도록 하는 경우를 찾아보자.

나의 풀이

import sys
input=sys.stdin.readline

def func():
    n,m=map(int,input().split())
    paper=[]
    for _ in range(n):
        paper.append(list(map(int,input().split())))
    tetro=[[(0,0),(0,1),(0,2),(0,3)],
           [(0,0),(1,0),(2,0),(3,0)],
           [(0,0),(1,0),(0,1),(1,1)],
           [(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),(1,2)],
           [(0,2),(1,1),(1,2),(1,0)],
           [(0,0),(0,1),(0,2),(1,2)],
           [(0,0),(1,0),(0,1),(0,2)],
           [(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,1),(1,0),(1,1),(1,2)],
           [(0,0),(0,1),(0,2),(1,1)],
           [(0,0),(1,0),(1,1),(2,0)],
           [(0,1),(1,1),(1,0),(2,1)]]
    
    maxs=0
    for x in range(n):
        for y in range(m):
            for i in tetro:
                s=0
                for j in range(4):
                    nx,ny=x+i[j][0],y+i[j][1]
                    if 0<=nx<n and 0<=ny<m:
                        s+=paper[nx][ny]
                    else:
                        s=0
                        break
                maxs=max(maxs,s)
    return maxs

print(func())

테트로미노 좌표를 어떻게 처리할까 했는데 질문게시판에서 좌표를 적어주신 글을 찾았다… 단순 브루트포스를 사용해 한 좌표에서 가능한 모든 테트로미노의 경우(19가지)를 전부 확인했다.

시간복잡도

테트로미노의 개수 19종이의 가로 500종이의 세로 500테트로미노를 이루는 정사각형 4 = 약 O(210^8)정도이다.