출처 : https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
정말 가능한 모든 경우에 대해서 브루트 포스하게 풀었다.
# Code
|
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
maxv = 0
for i in range(0, N-3):
for j in range(M):
x = board[i][j] + board[i+1][j] + board[i+2][j] + board[i+3][j]
if maxv < x: maxv = x
for i in range(N):
for j in range(0, M-3):
x = board[i][j] + board[i][j+1] + board[i][j+2] + board[i][j+3]
if maxv < x: maxv = x
for i in range(0, N-1):
for j in range(0, M-1):
x = board[i][j] + board[i][j+1] + board[i+1][j] + board[i+1][j+1]
if maxv < x: maxv = x
for i in range(0, N-2):
for j in range(0, M-1):
x = board[i][j] + board[i+1][j] + board[i+2][j] + board[i+2][j+1]
if maxv < x: maxv = x
x = board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+2][j+1]
if maxv < x: maxv = x
x = board[i][j] + board[i+1][j] + board[i+2][j] + board[i][j+1]
if maxv < x: maxv = x
x = board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+2][j+1]
if maxv < x: maxv = x
x = board[i][j] + board[i+1][j] + board[i+2][j] + board[i+1][j+1]
if maxv < x: maxv = x
for i in range(0, N-1):
for j in range(0, M-2):
x = board[i][j] + board[i+1][j] + board[i][j+1] + board[i][j+2]
if maxv < x: maxv = x
x = board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+1][j+2]
if maxv < x: maxv = x
x = board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j+2]
if maxv < x: maxv = x
x = board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+1][j+2]
if maxv < x: maxv = x
x = board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j+1]
if maxv < x: maxv = x
for i in range(1, N):
for j in range(0, M-2):
x = board[i][j] + board[i][j+1] + board[i][j+2] + board[i-1][j+2]
if maxv < x: maxv = x
x = board[i][j] + board[i][j+1] + board[i-1][j+1] + board[i-1][j+2]
if maxv < x: maxv = x
x = board[i][j] + board[i][j+1] + board[i-1][j+1] + board[i][j+2]
if maxv < x: maxv = x
for i in range(2, N):
for j in range(0, M-1):
x = board[i][j] + board[i][j+1] + board[i-1][j+1] + board[i-2][j+1]
if maxv < x: maxv = x
x = board[i][j] + board[i-1][j] + board[i-1][j+1] + board[i-2][j+1]
if maxv < x: maxv = x
for i in range(2, N):
for j in range(1, M):
x = board[i][j] + board[i-1][j] + board[i-1][j-1] + board[i-2][j]
if maxv < x: maxv = x
print(maxv)
|
cs |
'알고리즘 > [Python] 백준' 카테고리의 다른 글
| (Python) 백준 17144번: 미세먼지 안녕! (0) | 2020.03.10 |
|---|---|
| (Python) 백준 15686번: 치킨 배달 (0) | 2020.03.10 |
| (Python) 백준 13458번: 시험 감독 (0) | 2020.03.06 |
| (Python) 백준 12100번: 2048 (Easy) (0) | 2020.03.04 |
| (Python) 백준 15684번: 사다리 조작 (0) | 2020.03.03 |