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

Problem

테트로미노 모양 하나를 배열에 두어 그 내부의 값이 최대가 되게 하는 문제

Solution

테트로미노가 가질수 있는 19개의 경우의 수를 모두 두어
for문으로 (0,0)부터 끝까지 체크한 뒤에 그 19개의 경우의수의 합을 더하는 문제

도저히 어떻게 풀어야할지 모르겠더라.
19개의 경우의수를 생각하는것도 풀이를 참조하였다.
빡세다 빡세... 19개의 경우의수를 모두 구하여, 각각의 경우를 브루트포스 한다라...


이런 문제는 한번 이해되면 이해 딱 되는데 그걸 생각해내기가 어렵네 ㅠ


출처: https://jeongchul.tistory.com/670

Python Code

import sys

graph=[]
h,w=map(int,sys.stdin.readline().split())

for _ in range(h):
    tmp=list(map(int,sys.stdin.readline().split()))
    graph.append(tmp)

tetromino=[
    [(0,0),(0,1),(0,2),(0,3)],
    [(0,0),(1,0),(2,0),(3,0)],

    [(0, 0), (0, 1), (1, 0), (1, 1)],


    [(0, 0), (1, 0), (2, 0), (2, 1)],
    [(0, 1), (1, 1), (2, 1), (2, 0)],
    [(0, 0), (0, 1), (0, 2), (1, 0)],
    [(0, 0), (0, 1), (0, 2), (1, 2)],
    [(0, 0), (0, 1), (1, 1), (2, 1)],
    [(0, 0), (0, 1), (1, 0), (2, 0)],
    [(0, 2), (1, 0), (1, 1), (1, 2)],
    [(0, 0), (1, 0), (1, 1), (1, 2)],


    [(0, 0), (1, 0), (1, 1), (2, 1)],
    [(0, 1), (1, 0), (1, 1), (2, 0)],
    [(0, 1), (0, 2), (1, 0), (1, 1)],
    [(0, 0), (0, 1), (1, 1), (1, 2)],

    [(0, 0), (0, 1), (0, 2), (1, 1)],
[(1, 0), (0, 1), (1, 1), (2, 1)],
[(0, 1), (1, 0), (1, 1), (1, 2)],
[(0, 0), (1, 0), (2, 0), (1, 1)]
    ]



ans=-1e9
def find(y,x):
    global ans
    for i in range(19):
        result=0
        for j in range(4):
            yy=y+tetromino[i][j][0]
            xx=x+tetromino[i][j][1]

            if yy<0 or xx<0 or yy>h-1 or xx>w-1:
                continue
            result+=graph[yy][xx]
        ans=max(ans,result)
for i in range(0,h):
    for j in range(0,w):
        find(i,j)
print(ans)