접근 : 배열을 돌리는 함수, 집어 넣을 수 있는지 확인 후 집어 넣는 함수를 구현해서 조건에 맞게 처리
챌린징 : 시간 초과
원인 : deepcopy를 너무 함부로 사용했다
비어있지 않은 공간이어도 스티커 전체를 기준으로 하면 안겹칠 수 있으니
0,0 ~ n,m까지 따지는 것은 맞으나, 하나씩 넣어보면서 '원본을 바꾸며' 잘못될 때마다 새로운
딥 카피를 만들어냈는데, 1600연산이 계속 곱해져서 기존의 찾는 함수에서 이미 256만 연산인데
1600이 또 곱해져서 거의 100억 가까이 되어버림
피씬 때 고생했듯이 N퀸과 유사하게 원본을 바꿔가면서 계속 할당해제하고 다시 복사하는 행위는 하지 않는다.
ㄴ> 원본을 바꿔가지 않고도 판단 할 수 있는 유형이라면 원본을 바꾸지 않는 것이 연산 최적화.
구현
import sys
import copy
def rot(arr):
y = len(arr)
x = len(arr[0])
new = [[0]*y for _ in range(x)]
for i in range(x):
for j in range(y):
new[i][j] = arr[y-1-j][i]
return new
# 회전하는 함수 구현 (기존 함수)
# 기존 함수의 y,x의 크기 측정
# 전환된 크기의 새로운 배열만들기
# new = [[0]*y for _ in range(x)]
# for i in range(x): 기존 x에 대한것이 y가 됌
# for j in range(y):
# new[i][j] = S[y-1-j][i]
def makenew(S,O,y,x):
k1 = len(S)
k2 = len(S[0])
for i in range(k1):
for j in range(k2):
if (O[y+i][x+j] + S[i][j]) > 1:
return False
for i in range(k1):
for j in range(k2):
O[y+i][x+j]+=S[i][j] #바로 바꾸지말고 다 돌고 나서 이슈가 없으면 붙혀넣기 > check에서 딥카피를 피할 수 있음 N퀸때와 유사함
return True
def check(S,O): #새로운 origin반환하게 바꾸자 check 한번에 연산이 거의 7억인데 딥카피 하게될때마다 1600번하면 백억은 우스운 연산이다.... 줄여햠
# 오리지날의 남은 크기와 스티커의 크기를 비교한다 크기자체가 x와 y모두 오리지널이 같거나 커야함 폴스리턴
k1 = len(S)
k2 = len(S[0])
neworigin = copy.deepcopy(O)
for y in range(n):
for x in range(m):
if ((y+k1) > n) or ((x+k2) > m): #무지성 딥카피 줄임
continue
else:
if (makenew(S,neworigin,y,x)):
return neworigin
del(neworigin)
return False
n,m,k = input().split()
n = int(n)
m = int(m)
k = int(k)
origin = [([0]*m) for _ in range(n)]
Sarr = []
for _ in range(k):
sy,sx = input().split()
sy=int(sy)
sx=int(sx)
temp = []
for __ in range(sy):
temp.append(list(map(int, sys.stdin.readline().strip().split())))
Sarr.append(temp)
# 회전 조건 > 크기가 맞지 않거나, 모든 좌표에서 찾아봤을 때 없는 경우
# 3회전 후에도 없으면 다음 스티커임
for S in Sarr:
St = S
rotate = 0
while(rotate <= 3):
sy = len(St)
sx = len(St[0])
if (sy > n) or (sx > m):
St = rot(St)
rotate+=1
continue
temp = check(St,origin)
if (temp):
to = origin
origin = temp
del(to)
break
St = rot(St)
rotate+=1
cnt = 0
for yy in range(n):
for xx in range(m):
if origin[yy][xx] == 1:
cnt+=1
print(cnt)
42Seoul