백준 / 테트로미노 / 14500

Question

문제링크
Gold 5

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

정사각형은 서로 겹치면 안 된다.
도형은 모두 연결되어 있어야 한다.
정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

Input

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1

Output

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

19

Logic

기본 구조 : brute

N X N 배열에서 어떤 '한 칸'을 기준으로 테트로미노 도형을 그린다고 가정하면, 왼쪽 위 칸부터 순차적으로 모든 경우의 수를 그려보며 최대값을 구할 수 있다.
이 때 기준이 되는 칸 부터 그리지 않고 기준이 되는 칸을 기점으로 n x n 칸 내에서 그리는 방법도 포함한다. ('ㅗ' 같이 왼쪽 위 기준 칸은 포함하지 않고 그리는 방식 말이다)

그림을 다시 봐보자.

어떤 '한 칸'을 기준으로 위 5가지 도형을 그려본다면,
하늘색 : 2가지
노란색 : 1가지
주황색 : 4가지
초록색 : 4가지
핑크색 : 4가지
로 총 15가지이다.

이상 15가지를 N X N 의 배열 안에서 오른쪽과 아래쪽으로 그릴 때, 남은 행과 열에 따라 15가지를 그릴 수 있는지 없는지 판단하여 그려본다.

Code

from sys import stdin

r,c = map(int,stdin.readline().split())

data=[]
for _ in range(r):
    buff = list(map(int,stdin.readline().split()))
    data.append(buff)

sums=0
for ir in range(r):
    for ic in range(c):
        # ㅣ
        if ir+3 < r : sums=max(sums,data[ir][ic] +data[ir+1][ic] +data[ir+2][ic]+data[ir+3][ic])
        # ㅡ
        if ic+3 < c : sums=max(sums,sum(data[ir][ic:ic+4]))
        if ir+2 < r and ic+1 < c :
            sums = max(sums,data[ir][ic+1] +data[ir+1][ic] +data[ir+1][ic+1]+data[ir+2][ic+1], data[ir][ic+1] +data[ir+1][ic] +data[ir+1][ic+1]+data[ir+2][ic], data[ir][ic+1] +data[ir+1][ic+1] +data[ir+2][ic]+data[ir+2][ic+1])
            sums = max(sums,data[ir][ic] +data[ir+1][ic] +data[ir+2][ic]+data[ir][ic+1])
            sums = max(sums,data[ir][ic] +data[ir+1][ic] +data[ir+1][ic+1]+data[ir+2][ic+1], data[ir][ic] +data[ir+1][ic] +data[ir+2][ic]+data[ir+1][ic+1])
            sums = max(sums,data[ir][ic] +data[ir][ic+1] +data[ir+1][ic+1]+data[ir+2][ic+1], data[ir][ic] +data[ir+1][ic] +data[ir+2][ic]+data[ir+2][ic+1])
        if ir+1 < r and ic+2 < c :
            sums = max(sums,data[ir][ic+1] +sum(data[ir+1][ic:ic+3]), data[ir][ic+1] +data[ir][ic+2] +data[ir+1][ic]+data[ir+1][ic+1], data[ir][ic+2] +sum(data[ir+1][ic:ic+3]))
            sums = max(sums,data[ir][ic] +data[ir+1][ic] +data[ir][ic+1]+data[ir][ic+2])
            sums = max(sums,data[ir][ic] +data[ir][ic+1] +data[ir+1][ic+1]+data[ir+1][ic+2], data[ir][ic] +data[ir][ic+1] +data[ir][ic+2]+data[ir+1][ic+1])
            sums = max(sums,data[ir][ic] +data[ir][ic+1] +data[ir][ic+2]+data[ir+1][ic+2], data[ir][ic] +data[ir+1][ic] +data[ir+1][ic+1]+data[ir+1][ic+2])
        # ㅁ
        if ir+1 < r and ic+1 < c :
            sums = max(sums,data[ir][ic] +data[ir+1][ic] +data[ir][ic+1]+data[ir+1][ic+1])

print(sums)