풀리자마자 기뻐서 올리기 때문에 코드 안 깔끔함 주의
문제
뭐 정사각형 네개를 잘 이어 붙이면 테트로미노라고 한다나. 입력으로는 2차원 배열이 주어지는데 각각의 칸은 1X1의 정사각형이고, 각각 자연수가 들어있다. 이 2차원 배열에 테트로미노를 잘 놓아서, 겹치는 부분의 합이 가장 크게 하는 것이 목표.
어떻게 생각했지?
전에 카카오였나에서 풀었던 열쇠 자물쇠 하위 호환 느낌이었다. 5개의 모양 하나씩 전부 판에 돌리고, 다 돌리면 90도 회전에서 돌리고 해서 4번 돌리면 되겠다고 생각했다.
어디서 헤맸지?
이런 구현 문제에 좀 약한 것 같다... 인덱스만 생각하면 머리가 너무 아프다..일단 각각의 도형에 해당하는 배열을 만들고, 맵에서 시작점(x,y)를 잡고 거기서 지금 움직이려는 도형의 좌표가 1이면 더하고 0이면 안더하고 하는 식으로 했다.
전에 카카오 문제가 자꾸 생각나가지고 오히려 더 헤맨 것 같기도 하다.. 그 때 어느 분 코드를 보니 인풋 배열을 XOR 시켜서 멋있게 풀었던거가 인상적이어서 자꾸 따라하려다 보니까 오히려 문제랑 약간 안 맞는 것 같고 그래서 더 오래 걸렸던 것 같당..
-
근데 여기서 맵의 좌표랑 도형의 좌표를 어떻게 매핑 시킬까 삽질을 막 나머지로 하고 그랬었는데 몹시 삽질이었다. 그냥 해당 시작점 x,y 찍고 거기를 도형의 시작점으로 삼아서 돌리면 되는 거였었는데..
-
그리고 대칭도 가능한 조건을 못봐가지고 한참 에러가 났다. 대칭도 가능한데, 몇몇 도형은 90도 회전하는 것으로만 해가지고는 대칭되는 부분을 잡지 못했다. 그래서 대칭이 회전으로 표현이 안되는 경우를 추가했다.
Code
import sys
from copy import deepcopy
maxval = 0
def rotated(tet):
list_of_tuples = zip(*tet[::-1])
return [list(elem) for elem in list_of_tuples]
def check(board, tet,n,m) :
global maxval
x_len = len(tet)
y_len = len(tet[0])
for startx in range(n) :
if startx + (x_len-1) >= n :
continue
for starty in range(m) :
sumval = 0
if starty+(y_len-1) >= m :
continue
for j in range(x_len) :
for i in range(y_len) :
if tet[j][i] == 1 :
sumval += board[startx+ j][starty+i]
maxval = max(sumval,maxval)
def solve() :
n , m = map(int,sys.stdin.readline().split())
board = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
tet1 = [[1,1,1,1]]
tet2 = [[1,1],[1,1]]
tet3 = [[1,0],[1,0],[1,1]]
tet4 = [[1,0],[1,1],[0,1]]
tet5 = [[1,1,1],[0,1,0]]
tet6 = [[0,1],[1,1],[1,0]]
tet7 = [[0,1],[0,1],[1,1]]
tet = [tet1,tet2,tet3,tet4,tet5,tet6,tet7]
for t in tet :
for _ in range(4):
check(board,t,n,m)
t = rotated(t)
print(maxval)
if __name__ == "__main__" :
solve()
굉장히 오래 걸린다. 완전탐색이니까 오래 걸리긴 하겠지만..아마 회전하는 배열 같은걸 잘 정리해서 더 최적화 시키는 것 같다.
