[삼성기출] 테트리스 블럭 안의 합 최대화 하기 - 파이썬

직관적으로 풀면, 

나올 수 있는 모든 블럭의 종류의 좌표값을 저장해서 해결한다. 

 

n,m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]

blocks = [[(0,1),(0,2),(0,3)],[(1,0),(2,0),(3,0)],		#연속 일자 모형
		[(0,1),(1,0),(1,1)],							#정사각형
        [(1,0),(1,1),(2,0)],[(1,0),(2,0),(1,-1)],[(0,1),(0,2),(-1,1)],[(0,1),(0,2),(1,1)],	#가운데 툭튀 형
        [(1,0),(1,1),(2,1)],[(1,0),(0,1),(-1,1)],[(0,1),(-1,1),(-1,2)],[(0,1),(1,1),(1,2)],	#계단형
        [(1,0),(2,0),(2,1)],[(0,1),(-1,1),(-2,1)],[(0,1),(1,0),(2,0)],[(0,1),(1,1),(2,1)],	#ㄱ,ㄴ 형
        [(0,1),(0,2),(-1,2)],[(1,0),(1,1),(1,2)],[(0,1),(0,2),(1,2)],[(0,1),(0,2),(1,0)]]

max_ = -100

for block in blocks:				#가능한 모든 블럭 모양에 대해
    for i in range(n):
        for j in range(m):
            tmp = arr[i][j]
            for ni, nj in block:	
                ni += i
                nj += j
                if 0<=ni<n and 0<=nj<m:		#해당 블럭의 값이 이차원 영역 안에 속할 때
                    tmp += arr[ni][nj]
                else:						#한 개라도 속하지 않으면 최대값을 구할 수 없으므로, break
                    break
            if tmp > arr[i][j]:				#현재 블럭의 합과 최대값 비교
                max_ = max(max_,tmp)
print(max_)