반응형
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
알고리즘 분류
- 구현
- 브루트포스 알고리즘
SOLUTION
import sys
def block(i, j):
global answer
for x in range(19):
result = 0
for y in range(4):
try:
next_x = i + tetromino[x][y][0] # X좌표
next_y = j + tetromino[x][y][1] # Y좌표
result += paper[next_x][next_y]
except IndexError:
continue
answer = max(answer, result)
N, M = map(int, sys.stdin.readline().split())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
answer = 0
# ㅁ으로 1가지, ㅡ로 2가지, ㄴ으로 8가지, ㅜ 으로 4가지, 나머지 모양으로 4가지 => 총 19 가지
tetromino = [
[(0,0), (0,1), (1,0), (1,1)],
[(0,0), (0,1), (0,2), (0,3)],
[(0,0), (1,0), (2,0), (3,0)],
[(0,0), (0,1), (0,2), (1,0)],
[(1,0), (1,1), (1,2), (0,2)],
[(0,0), (1,0), (1,1), (1,2)],
[(0,0), (0,1), (0,2), (1,2)],
[(0,0), (1,0), (2,0), (2,1)],
[(2,0), (2,1), (1,1), (0,1)],
[(0,0), (0,1), (1,0), (2,0)],
[(0,0), (0,1), (1,1), (2,1)],
[(0,0), (0,1), (0,2), (1,1)],
[(1,0), (1,1), (1,2), (0,1)],
[(0,0), (1,0), (2,0), (1,1)],
[(1,0), (0,1), (1,1), (2,1)],
[(1,0), (2,0), (0,1), (1,1)],
[(0,0), (1,0), (1,1), (2,1)],
[(1,0), (0,1), (1,1), (0,2)],
[(0,0), (0,1), (1,1), (1,2)]
]
for i in range(N):
for j in range(M):
block(i, j)
print(answer)'코딩테스트 대비 > BOJ' 카테고리의 다른 글
| [Baekjoon/Python] 2407번: 조합 - 효과는 굉장했다! (0) | 2022.03.14 |
|---|---|
| [Baekjoon/Python] 9019번: DSLR - 효과는 굉장했다! (0) | 2022.03.09 |
| [Baekjoon/Python] 10026번: 적록색약 - 효과는 굉장했다! (0) | 2022.03.09 |
| [Baekjoon/Python] 7662번: 이중 우선순위 큐 - 효과는 굉장했다! (0) | 2022.03.09 |
| [Baekjoon/Python] 7569번: 토마토 - 효과는 굉장했다! (0) | 2022.03.09 |