[백준14500] 테트로미노

문제

---

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

14500번: 테트로미노

 

생각의 흐름

---

1. 최댓값을 구하기 위해 필요한 규칙성이 없음을 발견 -> 즉, 브루트포스로 모든 경우를 계산해봐야 함
2. 모든 경우란 무엇인가? -> 가능한 모든 테트로미노의 모양(회전과 대칭을 이용)

 

깨달은 점

---

복잡한 brute-force 문제에서는 case를 빠뜨리지 않고 자세하게 분류하는 것이 중요!!

코드

---

N, M = list(map(int, input().split()))
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))
set_of_sum = []

def square_shape():
    for i in range(N-1):
        for j in range(M-1):
            sum = arr[i][j]+arr[i+1][j]+arr[i][j+1]+arr[i+1][j+1]
            set_of_sum.append(sum)

def I_shape():
    for i in range(N):
        for j in range(M-3):
            sum = arr[i][j]+arr[i][j+1]+arr[i][j+2]+arr[i][j+3]
            set_of_sum.append(sum)
    for j in range(M):
        for i in range(N-3):
            sum = arr[i][j]+arr[i+1][j]+arr[i+2][j]+arr[i+3][j]
            set_of_sum.append(sum)

def L_shape():
    for i in range(N-2):
        for j in range(M-1):
            sum = arr[i][j]+arr[i+1][j]+arr[i+2][j]+arr[i+2][j+1]
            set_of_sum.append(sum)
    for i in range(N-1):
        for j in range(M-2):
            sum = arr[i][j]+arr[i+1][j]+arr[i][j+1]+arr[i][j+2]
            set_of_sum.append(sum)
    for i in range(N-2):
        for j in range(M-1):
            sum = arr[i][j]+arr[i][j+1]+arr[i+1][j+1]+arr[i+2][j+1]
            set_of_sum.append(sum)
    for i in range(N-1):
        for j in range(M-2):
            sum = arr[i][j+2]+arr[i+1][j]+arr[i+1][j+1]+arr[i+1][j+2]
            set_of_sum.append(sum)
    for i in range(N-2):
        for j in range(M-1):
            sum = arr[i][j]+arr[i][j+1]+arr[i+1][j]+arr[i+2][j]
            set_of_sum.append(sum)
    for i in range(N-2):
        for j in range(M-1):
            sum = arr[i][j+1]+arr[i+1][j+1]+arr[i+2][j]+arr[i+2][j+1]
            set_of_sum.append(sum)
    for i in range(N-1):
        for j in range(M-2):
            sum = arr[i][j]+arr[i+1][j]+arr[i+1][j+1]+arr[i+1][j+2]
            set_of_sum.append(sum)
    for i in range(N-1):
        for j in range(M-2):
            sum = arr[i][j]+arr[i][j+1]+arr[i][j+2]+arr[i+1][j+2]
            set_of_sum.append(sum)

def S_shape():
    for i in range(N-2):
        for j in range(M-1):
            sum = arr[i][j]+arr[i+1][j]+arr[i+1][j+1]+arr[i+2][j+1]
            set_of_sum.append(sum)
    for i in range(N-1):
        for j in range(M-2):
            sum = arr[i][j+1]+arr[i][j+2]+arr[i+1][j]+arr[i+1][j+1]
            set_of_sum.append(sum)
    for i in range(N-2):
        for j in range(M-1):
            sum = arr[i][j+1]+arr[i+1][j]+arr[i+1][j+1]+arr[i+2][j]
            set_of_sum.append(sum)
    for i in range(N-1):
        for j in range(M-2):
            sum  = arr[i][j]+arr[i][j+1]+arr[i+1][j+1]+arr[i+1][j+2]
            set_of_sum.append(sum)

def T_shape():
    for i in range(N-1):
        for j in range(M-2):
            sum = arr[i][j]+arr[i][j+1]+arr[i][j+2]+arr[i+1][j+1]
            set_of_sum.append(sum)
    for i in range(N-2):
        for j in range(M-1):
            sum = arr[i+1][j]+arr[i][j+1]+arr[i+1][j+1]+arr[i+2][j+1]
            set_of_sum.append(sum)
    for i in range(N-1):
        for j in range(M-2):
            sum = arr[i][j+1]+arr[i+1][j]+arr[i+1][j+1]+arr[i+1][j+2]
            set_of_sum.append(sum)
    for i in range(N-2):
        for j in range(M-1):
            sum = arr[i][j]+arr[i+1][j]+arr[i+1][j+1]+arr[i+2][j]
            set_of_sum.append(sum)

if __name__=='__main__':

    square_shape()
    I_shape()
    L_shape()
    S_shape()
    T_shape()

    print(max(set_of_sum))