14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
tetro1_1 = [[0,0], [0,1], [0,2], [0,3]]
tetro1_2 = [[0,0], [1,0], [2,0], [3,0]]
tetro1 = [tetro1_1, tetro1_2]
tetro2_1 = [[0,0], [0,1], [1,0], [1,1]]
tetro2 = [tetro2_1]
tetro3_1 = [[0,0], [1,0], [2,0] ,[2,1]]
tetro3_2 = [[0,1], [1,1], [2,1] ,[2,0]]
tetro3_3 = [[0,0], [0,1], [0,2] ,[1,0]]
tetro3_4 = [[0,0], [0,1], [0,2] ,[1,2]]
tetro3_5 = [[0,0], [1,0], [2,0] ,[0,1]]
tetro3_6 = [[0,1], [1,1], [2,1] ,[0,0]]
tetro3_7 = [[0,0], [1,0], [1,1] ,[1,2]]
tetro3_8 = [[0,2], [1,2], [1,1] ,[1,0]]
tetro3 = [tetro3_1,tetro3_2,tetro3_3,tetro3_4,tetro3_5,tetro3_6,tetro3_7,tetro3_8]
tetro4_1 = [[0,0], [1,0], [1,1], [2,1]]
tetro4_2 = [[0,1], [1,1], [1,0], [2,0]]
tetro4_3 = [[0,0], [0,1], [1,1], [1,2]]
tetro4_4 = [[1,0], [1,1], [0,1], [0,2]]
tetro4 = [tetro4_1,tetro4_2,tetro4_3,tetro4_4]
tetro5_1 = [[0,0], [0,1], [0,2], [1,1]]
tetro5_2 = [[0,1], [1,0], [1,1], [1,2]]
tetro5_3 = [[1,0], [0,1], [1,1], [2,1]]
tetro5_4 = [[0,0], [1,0], [1,1], [2,0]]
tetro5 = [tetro5_1,tetro5_2,tetro5_3,tetro5_4]
tetros = [tetro1, tetro2, tetro3, tetro4, tetro5]
ans = 0
for i in range(N):
for j in range(M):
for tetro in tetros:
for tetro_shape in tetro:
enable_move = True
for k in range(len(tetro_shape)):
position_n = tetro_shape[k][0]+i
position_m = tetro_shape[k][1]+j
if position_n >= N or position_m >= M:
enable_move = False
break
if enable_move:
temp = 0
for k in range(len(tetro_shape)):
position_n = tetro_shape[k][0]+i
position_m = tetro_shape[k][1]+j
temp+=board[position_n][position_m]
ans = max(ans, temp)
print(ans)
전형적인 브루트포스.
이 문제는 아무것도 안보고 1 try 만에 풀었다.
이 문제를 보면서 머신러닝 공부할때 CNN 을 직접 구현한 것과 비슷했다. stride 1 짜리 필터를 여러개 적용하는걸 직접 구현했었는데
그것과 굉장히 유사한 느낌이었다.
전체적으로
각 테트로미노가 회전,대칭했을때의 모든 모양의 좌표를 저장해놓고 board 에서 왼쪽 위부터 한칸씩 이동하면서 모든 블럭에 적용해보고 최대값을 저장하는것으로 특별히 어려울게 없는 문제였다.
브루트포스 매우순한맛.