[백준18808] 스티커 붙이기

https://www.acmicpc.net/problem/18808

 

 

링크 참고

 

문제 해결 방법

시간복잡도를 고려햐여 문제를 잘 읽고 그대로 구현하면 됨.

아래의 조건을 고려하여 코드를 작성하였음.

 

• 노트북에 스티커를 붙이기전에 모눈종이의 크기만으로 노트북에 들어갈 수 있는지 확인한다. 
  
  • 모눈종이의 행이 노트북의 행의 크기를 넘거나 모눈종이의 열이 노트북의 열의 크기를 넘는 경우, 모눈종이의 행과 열을 뒤집었을때(90도 회전한다고 가정했을때)도 노트북의 범위를 벗어나는지 확인한다. 
    
    • 범위를 벗어나지 않는다면 90도 회전
    • 범위를 벗어난다면 다음 스티커로 넘어간다. 
• 노트북에 모눈종이의 크기가 들어갈 수 있을때, 노트북의 빈곳에 스티커를 붙이는 시도를 한다. 
• 노트북에 붙여진 스티커의 현황과 스티커는 겹쳐도 되지만, 붙이려는 스티커의 빈칸이 노트북에 붙여진 스티커 일부를 지워서는 안된다.(모눈종이 전체를 붙이려고 할 경우 주의)
• 노트북에 스티커를 붙일때 회전을 먼저 해서는 안되고 일단 생긴 그대로 붙이려는 시도를 반드시 해야한다. 
  • 그 후 90도 회전을 3번 할 수 있다. (단, 90, 180, 270 순으로 진행해야함)
  • 3번의 회전이 끝나면 더이상의 회전은 의미가 없으므로, 스티커를 버린다.(다음 스티커로 넘어간다. )

 

코드 구현

 

시간초과난 코드 1

import sys, copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님

# 다른 스티커와 겹침X, 노트북 벗어나면X, 
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽) 

# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기

# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?

#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)

n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
    #모눈종이의 행, 열
    r, c = map(int, sys.stdin.readline().split()) 
    stickerPocketEntire.append([r,c])
    tmp2=[]
    for j in range(r):
        tmp1 = list(map(int, sys.stdin.readline().split()))
        tmp2.append(tmp1)
    stickerPocket.append(tmp2)

print(stickerPocket)

#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임. 
# 단, 붙일 수 없는 경우는 판별해줌 
# 붙일 수 없는 경우
#   1. 노트북을 벗어나는경우[조건문]
#   2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
#   ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
#   ->다음 스티커로 넘어간다. 

# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다. 

visited=[ [0] * m for i in range(n)]

print('visited', visited)

def rotation(cnt, i):
    
    r, l = stickerPocketEntire[i]
    # 3번만 돌림 
    
    #90도로 돌리기 
    tmp = stickerPocket[i]
    nn=len(tmp) 
    mm=len(tmp[0])
    tmpList =[]
    for qq in range(mm):
        tmpList2=[]
        for pp in range(nn-1, -1, -1):
            tmpList2.append(tmp[pp][qq])
        tmpList.append(tmpList2)
    stickerPocket[i]=tmpList
    stickerPocketEntire[i]=[mm, nn]
    print('checkcnt: ', cnt)
    cnt+=1
    print('cnt: ', cnt)
    return cnt

def backtrack(p, q, i, r, l, visited):
    rem = copy.deepcopy(visited)
    print('초기 rem', rem)
    # 이부분 백트래킹으로 구현해야할듯 
    for j in range(r):
        for jj in range(l):
            #왼쪽 위부터 조회
            nr = p+j
            nl = q+jj
            if 0<=nr<n and 0<=nl<m:
                print('i:', i, "j:", j, "jj", jj)
                if stickerPocket[i][j][jj]==1:
                    #두번째 스티커를 자리에 붙여본다
                    if visited[p+j][q+jj]!=1:
                        #겹치는지 확인후 붙여보기
                        visited[p+j][q+jj]=1
                    else:
                        #겹친다.
                        #스티커를 붙이기 전으로 원래대로 돌아가기 
                        visited=copy.deepcopy(rem)
                        check = 0
                        print('리턴 visited', visited)
                        return visited, check
                check = 1
            else:
                print("뭐지 nr:", nr, "nl:", nl)
                visited=copy.deepcopy(rem)
                check = 0
                print('리턴 visited', visited)
                return visited, check
                
    if check == 1:
        return visited, check

i=0
cnt=0 # 회전 횟수
check=1
while(1):
    r, l = stickerPocketEntire[i]
    if (n<r or m<l) or check ==0: 
        # 모눈종이의 크기가 노트북을 넘어가면
        # 90도 회전 적용
        if cnt <=3:
            cnt = rotation(cnt, i)
            r, l = stickerPocketEntire[i]
        else:
            i+=1
            cnt=0
                
    if i == 0:
        #항상 0,0에서 부터 시작해야함
        for j in range(r):
            for jj in range(l):
                if stickerPocket[0][j][jj]==1:
                    visited[j][jj]=1
        i+=1
        cnt=0
    else:
        for p in range(n):
            for q in range(m):
                if i ==k:
                    break
                
                print('hi')
                print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                visited, check = backtrack(p, q, i, r, l, visited)
                print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                print('hi end')
                if check==1 or cnt>3: #스티커를 제대로 붙였을 때
                    i+=1
                    cnt=0

                if check==0 and cnt>3:
                    break
            if check==0 and cnt>3:
                break

    if i ==k:
        break

print("?????????")
sum=0
for end in visited:
    for end2 in end:
        if end2==1:
            sum+=1
print(sum)

 

 

시간초과난 코드 2

import sys, copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님

# 다른 스티커와 겹침X, 노트북 벗어나면X, 
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽) 

# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기

# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?

#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)

n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
    #모눈종이의 행, 열
    r, c = map(int, sys.stdin.readline().split()) 
    stickerPocketEntire.append([r,c])
    tmp2=[]
    for j in range(r):
        tmp1 = list(map(int, sys.stdin.readline().split()))
        tmp2.append(tmp1)
    stickerPocket.append(tmp2)

print(stickerPocket)

#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임. 
# 단, 붙일 수 없는 경우는 판별해줌 
# 붙일 수 없는 경우
#   1. 노트북을 벗어나는경우[조건문]
#   2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
#   ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
#   ->다음 스티커로 넘어간다. 

# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다. 

visited=[ [0] * m for i in range(n)]

print('visited', visited)

def rotation(cnt, i):
    
    r, l = stickerPocketEntire[i]
    # 3번만 돌림 
    
    #90도로 돌리기 
    tmp = stickerPocket[i]
    nn=len(tmp) 
    mm=len(tmp[0])
    tmpList =[]
    for qq in range(mm):
        tmpList2=[]
        for pp in range(nn-1, -1, -1):
            tmpList2.append(tmp[pp][qq])
        tmpList.append(tmpList2)
    print('before',stickerPocket[i])
    stickerPocket[i]=tmpList
    
    stickerPocketEntire[i]=[mm, nn]
    print('after',tmpList)
    print('checkcnt: ', cnt)
    cnt+=1
    print('cnt: ', cnt)
    return cnt

def backtrack(p, q, i, r, l, visited):
    rem = copy.deepcopy(visited)
    print('초기 rem', rem)
    # 이부분 백트래킹으로 구현해야할듯 
    for j in range(r):
        for jj in range(l):
            #왼쪽 위부터 조회
            nr = p+j
            nl = q+jj
            if 0<=nr<n and 0<=nl<m:
                print('i:', i, "j:", j, "jj", jj)
                if stickerPocket[i][j][jj]==1:
                    #두번째 스티커를 자리에 붙여본다
                    if visited[p+j][q+jj]!=1:
                        #겹치는지 확인후 붙여보기
                        visited[p+j][q+jj]=1
                    else:
                        #겹친다.
                        #스티커를 붙이기 전으로 원래대로 돌아가기 
                        visited=copy.deepcopy(rem)
                        check = 0
                        print('리턴 visited', visited)
                        return visited, check
                check = 1
            else:
                print("뭐지 nr:", nr, "nl:", nl)
                visited=copy.deepcopy(rem)
                check = 0
                print('리턴 visited', visited)
                return visited, check
                
    if check == 1:
        return visited, check

i=0
cnt=0 # 회전 횟수
check=1
while(1):
    r, l = stickerPocketEntire[i]
    if (n<r or m<l) or check ==0: 
        if l<=n and r<=m:
        # 모눈종이의 크기가 노트북을 넘어가면
        # 90도 회전 적용
        # 회전의 조건: 모눈종이가 노트북에 딱 들어맞지 않는경우(단, 가로 세로는 뒤집혔을때 노트북에 들어갈 수 있어야 함)
            if cnt <3:
                cnt = rotation(cnt, i)
                r, l = stickerPocketEntire[i]
            else:
                i+=1
                cnt=0
        else:
            i+=1
    
    if i == 0:
        #항상 0,0에서 부터 시작해야함
        for j in range(r):
            for jj in range(l):
                if stickerPocket[0][j][jj]==1:
                    visited[j][jj]=1
        i+=1
        cnt=0
    else:
        for p in range(n):
            for q in range(m):
                if i ==k:
                    break
                r, l = stickerPocketEntire[i]
                print('hi')
                print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                visited, check = backtrack(p, q, i, r, l, visited)
                print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                print('hi end')
                if check==1 or cnt>3: #스티커를 제대로 붙였을 때
                    i+=1
                    cnt=0

                if check==0 and cnt>3:
                    break
            if check==0 and cnt>3:
                break

    if i ==k:
        break

print("?????????")
sum=0
for end in visited:
    for end2 in end:
        if end2==1:
            sum+=1
print(sum)

 

 

시간초과 해결후 틀린 코드 1

import sys, copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님

# 다른 스티커와 겹침X, 노트북 벗어나면X, 
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽) 

# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기

# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?

#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)

n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
    #모눈종이의 행, 열
    r, c = map(int, sys.stdin.readline().split()) 
    stickerPocketEntire.append([r,c])
    tmp2=[]
    for j in range(r):
        tmp1 = list(map(int, sys.stdin.readline().split()))
        tmp2.append(tmp1)
    stickerPocket.append(tmp2)

#print(stickerPocket)

#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임. 
# 단, 붙일 수 없는 경우는 판별해줌 
# 붙일 수 없는 경우
#   1. 노트북을 벗어나는경우[조건문]
#   2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
#   ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
#   ->다음 스티커로 넘어간다. 

# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다. 

visited=[[0] * m for i in range(n)]

#print('visited', visited)

def rotation(cnt, i):
    
    r, l = stickerPocketEntire[i]
    # 3번만 돌림 
    
    #90도로 돌리기 
    tmp = stickerPocket[i]
    nn=len(tmp) 
    mm=len(tmp[0])
    tmpList =[]
    for qq in range(mm):
        tmpList2=[]
        for pp in range(nn-1, -1, -1):
            tmpList2.append(tmp[pp][qq])
        tmpList.append(tmpList2)
    #print('before',stickerPocket[i])
    stickerPocket[i]=tmpList
    
    stickerPocketEntire[i]=[mm, nn]
    # print('after',tmpList)
    # print('checkcnt: ', cnt)
    cnt+=1
    # print('cnt: ', cnt)
    return cnt

def backtrack(p, q, i, r, l, visited):
    rem = copy.deepcopy(visited)
    # print('초기 rem', rem)
    # 이부분 백트래킹으로 구현해야할듯 
    for j in range(r):
        for jj in range(l):
            #왼쪽 위부터 조회
            nr = p+j
            nl = q+jj
            if 0<=nr<n and 0<=nl<m:
                # print('i:', i, "j:", j, "jj", jj)
                if stickerPocket[i][j][jj]==1:
                    #두번째 스티커를 자리에 붙여본다
                    if visited[p+j][q+jj]!=1:
                        #겹치는지 확인후 붙여보기
                        visited[p+j][q+jj]=1
                    else:
                        #겹친다.
                        #스티커를 붙이기 전으로 원래대로 돌아가기 
                        visited=copy.deepcopy(rem)
                        check = 0
                        # print('리턴 visited', visited)
                        return visited, check
                check = 1
            else:
                # print("뭐지 nr:", nr, "nl:", nl)
                visited=copy.deepcopy(rem)
                check = 0
                # print('리턴 visited', visited)
                return visited, check
                
    if check == 1:
        return visited, check

i=0
cnt=0 # 회전 횟수
check=1
while(1):
    r, l = stickerPocketEntire[i]
    if (n<r or m<l) or check ==0: 
        if l<=n and r<=m:
        # 모눈종이의 크기가 노트북을 넘어가면
        # 90도 회전 적용
        # 회전의 조건: 모눈종이가 노트북에 딱 들어맞지 않는경우(단, 가로 세로는 뒤집혔을때 노트북에 들어갈 수 있어야 함)
            if cnt <3:
                cnt = rotation(cnt, i)
                r, l = stickerPocketEntire[i]
            else:
                i+=1
                cnt=0
        else:
            i+=1
    
    if i == 0:
        #항상 0,0에서 부터 시작해야함
        for j in range(r):
            for jj in range(l):
                if stickerPocket[0][j][jj]==1:
                    visited[j][jj]=1
        i+=1
        cnt=0
    else:
        for p in range(n):
            for q in range(m):
                if i ==k:
                    break
                r, l = stickerPocketEntire[i]
                # print('hi')
                # print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                visited, check = backtrack(p, q, i, r, l, visited)
                # print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                # print('hi end')
                if check==1 or cnt>3: #스티커를 제대로 붙였을 때
                    i+=1
                    cnt=0

                if check==0 and cnt>3:
                    break
            if check==0 and cnt>3:
                break

    if i ==k:
        break

#print("?????????")
sum=0
for end in visited:
    for end2 in end:
        if end2==1:
            sum+=1
print(sum)

 

 

시간초과 해결후 틀린 코드 2

import sys
#import copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님

# 다른 스티커와 겹침X, 노트북 벗어나면X, 
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽) 

# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기

# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?

#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)

n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
    #모눈종이의 행, 열
    r, c = map(int, sys.stdin.readline().split()) 
    stickerPocketEntire.append([r,c])
    tmp2=[]
    for j in range(r):
        tmp1 = list(map(int, sys.stdin.readline().split()))
        tmp2.append(tmp1)
    stickerPocket.append(tmp2)

#print(stickerPocket)

#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임. 
# 단, 붙일 수 없는 경우는 판별해줌 
# 붙일 수 없는 경우
#   1. 노트북을 벗어나는경우[조건문]
#   2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
#   ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
#   ->다음 스티커로 넘어간다. 

# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다. 

visited=[[0] * m for i in range(n)]

#print('visited', visited)

def rotation(cnt, i):
    
    r, l = stickerPocketEntire[i]
    # 3번만 돌림 
    
    #90도로 돌리기 
    tmp = stickerPocket[i]
    nn=len(tmp) 
    mm=len(tmp[0])
    tmpList =[]
    for qq in range(mm):
        tmpList2=[]
        for pp in range(nn-1, -1, -1):
            tmpList2.append(tmp[pp][qq])
        tmpList.append(tmpList2)
    #print('before',stickerPocket[i])
    stickerPocket[i]=tmpList
    
    stickerPocketEntire[i]=[mm, nn]
    # print('after',tmpList)
    # print('checkcnt: ', cnt)
    cnt+=1
    # print('cnt: ', cnt)
    return cnt

def backtrack(p, q, i, r, l, visited):
    #rem = copy.deepcopy(visited)
    rem = [item[:] for item in visited]
    # print('초기 rem', rem)
    # 이부분 백트래킹으로 구현해야할듯 
    for j in range(r):
        for jj in range(l):
            #왼쪽 위부터 조회
            nr = p+j
            nl = q+jj
            if 0<=nr<n and 0<=nl<m:
                # print('i:', i, "j:", j, "jj", jj)
                if stickerPocket[i][j][jj]==1:
                    #두번째 스티커를 자리에 붙여본다
                    if visited[p+j][q+jj]!=1:
                        #겹치는지 확인후 붙여보기
                        visited[p+j][q+jj]=1
                    else:
                        #겹친다.
                        #스티커를 붙이기 전으로 원래대로 돌아가기 
                        #visited=copy.deepcopy(rem)
                        visited=[item[:] for item in rem]
                        check = 0
                        # print('리턴 visited', visited)
                        return visited, check
                check = 1
            else:
                # print("뭐지 nr:", nr, "nl:", nl)
                #visited=copy.deepcopy(rem)
                visited = [item[:] for item in rem]
                check = 0
                # print('리턴 visited', visited)
                return visited, check
                
    if check == 1:
        return visited, check

i=0
cnt=0 # 회전 횟수
check=1
while(1):
    r, l = stickerPocketEntire[i]
    if (n<r or m<l) or check ==0: 
        if l<=n and r<=m:
        # 모눈종이의 크기가 노트북을 넘어가면
        # 90도 회전 적용
        # 회전의 조건: 모눈종이가 노트북에 딱 들어맞지 않는경우(단, 가로 세로는 뒤집혔을때 노트북에 들어갈 수 있어야 함)
            if cnt <3:
                cnt = rotation(cnt, i)
                r, l = stickerPocketEntire[i]
            else:
                i+=1
                cnt=0
        else:
            i+=1
    
    if i == 0:
        #항상 0,0에서 부터 시작해야함
        for j in range(r):
            for jj in range(l):
                if stickerPocket[0][j][jj]==1:
                    visited[j][jj]=1
        i+=1
        cnt=0
    else:
        for p in range(n):
            for q in range(m):
                if i ==k:
                    break
                r, l = stickerPocketEntire[i]
                # print('hi')
                # print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                visited, check = backtrack(p, q, i, r, l, visited)
                # print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                # print('hi end')
                if check==1 or cnt>3: #스티커를 제대로 붙였을 때
                    i+=1
                    cnt=0

                if check==0 and cnt>3:
                    break
            if check==0 and cnt>3:
                break

    if i ==k:
        break

#print("?????????")
sum=0
for end in visited:
    for end2 in end:
        if end2==1:
            sum+=1
print(sum)

정답 코드

 

import sys

n, m, k = map(int, sys.stdin.readline().split())

# 스티커 받고, 스티커 함에 넣기 
stickerPocket = []     # 모눈종이 각각 map 모음
stickerPocketEntire=[] # 모눈종이 r, l 모아놓는 함
for i in range(k):
    #모눈종이의 행, 열
    r, c = map(int, sys.stdin.readline().split()) 
    stickerPocketEntire.append([r,c])
    sticker=[]
    for j in range(r):
        tmp = list(map(int, sys.stdin.readline().split()))
        sticker.append(tmp)
    stickerPocket.append(sticker)

# 붙여졌나요?
visited=[[0] * m for i in range(n)]

# 90도 회전 함수
def rotation(cnt, i): 
    r, l = stickerPocketEntire[i] 
    # (90, 180, 270)도에 해당하게끔 3번만 돌림 
    
    sticker = stickerPocket[i]
    nn=len(sticker) # 기존의 행을 열로 사용
    mm=len(sticker[0]) # 기존의 열을 행으로 사용
    newSticker =[]

    for qq in range(mm):
        tmp=[]
        for pp in range(nn-1, -1, -1):
            tmp.append(sticker[pp][qq])
        newSticker.append(tmp)
    stickerPocket[i]=newSticker
    stickerPocketEntire[i]=[mm, nn]
    # 회전카운트 증가시킴
    cnt+=1  
    return cnt

def backtrack(p, q, i, visited):
    # 스티커를 붙일 수 없을 경우, 붙이려는 스티커를 붙이기 전 상태로 돌아오기위한것 
    rem = [item[:] for item in visited]
    # 붙이려는 스티커의 행열 조회
    r, c = stickerPocketEntire[i] 
    for j in range(r): # 행
        for jj in range(c): # 열
            #왼쪽 위부터 조회
            nr = p+j # 행/ 기존 행:n
            nc = q+jj # 열/ 기존 열:m
            # 스티커가 노트북 범위 안에 들어오면
            if 0<=nr<n and 0<=nc<m: 
                # 모눈종이에서 붙여야 하는 지점인 경우 
                if stickerPocket[i][j][jj]==1:
                    # 미리 붙여진 스티커가 없다.
                    if visited[nr][nc]!=1:
                        # 스티커 붙이기 
                        check = 1
                        visited[p+j][q+jj]=1
                    # 미리 붙여진 스티커가 있다. 겹친다.
                    else:
                        # 스티커를 붙이기 전(원래대로)으로 돌아가기 
                        visited=[item[:] for item in rem]
                        # 스티커를 못붙였다는 표식
                        check = 0
                        return visited, check
                # 모눈종이에서 빈칸인 경우
                else:
                    continue
            # 스티커가 노트북 범위 안에 못을어오면
            else:
                # 노트북 원상복구
                visited = [item[:] for item in rem]
                # 스티커를 못붙였다는 표식
                check = 0
                return visited, check
    # 스티커를 정상적으로 붙인 경우
    if check == 1:
        return visited, check

# 시작 스티커 번호
i=0
# 붙일 스티커 번호가 증가한 후 한번도 스티커를 회전한적 없는경우를 가리기 위한 변수
first=1
# 회전 횟수
cnt=0 
# 스티커를 붙이지 않았다는 표식
check=0
needRotation=0
while(1):
    rotat=0
    
    # 붙일 스티커가 없는 경우 종료 
    if i == k:
        break

    # 스티커의 행 열
    r, c = stickerPocketEntire[i]

    # 스티커의 행이나 열중 하나가 노트북을 벗어나는 경우
    if n<r or m<c: 
        #스티커의 행을 열로, 열을 행으로 바꿨을때(회전했을 때) 노트북에 들어가는 경우
        if c<=n and r<=m: 
            if cnt <3: # 0-0, 90-1, 180-2, 270-3
                cnt = rotation(cnt, i)
                rotat = 1
            # 회전을 4번다 한 경우, 다음 스티커로 넘어감 
            else:
                i+=1
                cnt=0
                first=1
        # 스티커의 행을 열로, 열을 행으로 바꿨을때(회전했을 때) 노트북에 안들어가는 경우=붙일 수 없는 경우
        elif c>n and r>m:
            # 다음 스티커로 넘어감 
            first=1
            i+=1
            cnt=0

    # 스티커가 붙여지지 않았고 0도 일때 스티커 붙이는 시도를 다 해본경우 
    # 회전이 270까지 되지 않은 경우=> 회전
    if check == 0 and first==0 and rotat==0 and needRotation==1:
        if cnt<=3:
            cnt = rotation(cnt, i)
        
    for p in range(n):
        for q in range(m):
            # 한번 돌았으면 first=0
            rotat=0
            first=0
            
            # 붙일 스티커가 없는 경우 종료 
            if i == k:
                break

            # 붙일 스티커 붙여보기 
            visited, check = backtrack(p, q, i, visited)
            #스티커를 제대로 붙였으면 빠져나감
            if check==1: 
                break
        #다음으로 붙일 스티커로 넘어가고, 회전 횟수 초기화
        #스티커를 붙였으면 빠져나감
        if check==1:
            check = 0
            i+=1
            cnt=0
            first=1
            needRotation=0
            break
    if check == 0:
        needRotation=1

    if cnt==3:
        i+=1
        first=1
        cnt=0

    # 붙일 스티커가 없는 경우 종료 
    if i ==k:
        break

# 노트북에 붙여진 스티커 개수 세기
sum=0
for end in visited:
    for end2 in end:
        if end2==1:
            sum+=1
print(sum)

 

시간/공간 복잡도

 

N(40)*M(40)*K(100) = 16000이라  1초 기준으로 NlogN으로 풀어야 하는 문제이다. 근데 문제에서 2초를 주엇으니 사실상

2NlogN인건가? 

스터디할 때 물어볼 것 

 

 

최적화 및 개선

 

• sys 모듈 sys.stdin.readline()을 사용하여 반복적으로 입력받을 때 input()에 비해 시간을 확 줄였음
• copy 모듈의 deepcopy함수는 시간을 많이 잡아먹으니, 다른 방식으로 리스트 복사를 해야 시간초과가 나지 않는다. 

 

 

어려웠던 점

문제를 정확하게 이해해야 빈틈없이 구현할 수 있다. 

시뮬레이션 문제는 빈틈없이 구현하는게 가장 중요한것 같다. 

 

알게된 것

• copy모듈의 deepcopy()함수는 시간을 많이 잡아먹는다. 따라서 다른 방법을 이용해야한다.(시간초과의 주범)