algorithm'''problem solve
[백준] 14500 - 테트로미노 (구현, 브루트포스)
JunHwa Park
2020. 10. 23. 15:10
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
shapes = (((0, 0), (1, 0), (2, 0), ((3, 0), (0, -1), (0, 1), (1, -1), (1, 1), (2, -1), (2, 1))),
((0, 0), (0, 1), (0, 2), ((0, 3), (-1, 0), (1, 0), (-1, 1), (1, 1), (-1, 2), (1, 2))),
((0, 0), (0, 1), (1, 0), (1, 1)),
((0, 0), (1, 0), (1, 1), (2, 1)),
((0, 1), (1, 0), (1, 1), (2, 0)),
((0, 0), (0, 1), (1, 1), (1, 2)),
((1, 0), (0, 1), (1, 1), (0, 2)))
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
answer = 0
def get_sum(y, x, li):
summation = 0
for l in li:
summation += graph[y + l[0]][x + l[1]]
return summation
for i in range(n):
for j in range(m):
for a in range(2):
for b in range(7):
try:
val = get_sum(i, j, shapes[a][:3] + shapes[a][3][b:b + 1])
if answer < val:
answer = val
except IndexError:
pass
for a in range(2, 7):
try:
val = get_sum(i, j, shapes[a])
if answer < val:
answer = val
except IndexError:
pass
print(answer)
|
cs |
도형 뒤집고, 돌린거 하나 하나 다 구현해서 브루트포스로 돌렸다. 화가 난다.
원래 인덱스 검사하는거 직접 짜는 편인데, 화나서 그냥 try except로 돌리고 ㅋㅋ
마지막으로, 충격적인건
같은 코드인데, 위는 PyPy3, 아래는 Python3이다.
PyPy가 빠른건 알았는데, 확실히 빠르다.
근데 메모리는 시간이 빠른 대신 엄청나게 잡아먹는다.
근데 테트로미노가 아니라 테트리미노 아니었나? 흐음..