17136번 – 색종이 붙이기

문제

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

풀이

코드

# 17136-색종이 붙이기

def 사용한색종이개수(papers):
  return 25 - sum([papers[i] for i in range(1, 6)])

def 범위가모두일인가(y, x, k):
  global board
  for i in range(y, y+k):
    for j in range(x, x+k):
      if board[i][j] == 0: return False
  return True

def 색종이붙이기(y, x, k):
  global board
  for i in range(y, y+k):
    for j in range(x, x+k):
      board[i][j] = 0
      
def 색종이떼기(y, x, k):
  global board
  for i in range(y, y+k):
    for j in range(x, x+k):
      board[i][j] = 1

def DFS(y, x):
  global board, papers, count
  if board[y][x] == 0:
    if x < 9: DFS(y, x+1)
    elif y < 9: DFS(y+1, 0)  
    else:
      count = min(count, 사용한색종이개수(papers))
      return
  else:
    for k in range(5, 0, -1):
      if papers[k] == 0: continue
      if (x+k) > 10 or (y+k) > 10: continue
      if 범위가모두일인가(y, x, k) is False: continue
      papers[k] = papers[k] - 1
      색종이붙이기(y, x, k)
      
      if x < 9: DFS(y, x+1)
      elif y < 9: DFS(y+1, 0)
      else:
        count = min(count, 사용한색종이개수(papers))
      
      색종이떼기(y, x, k)
      papers[k] = papers[k] + 1
      
    
def answer():
  global board, papers, count
  DFS(0, 0)
  if count == 10**9+1: print(-1)
  else: print(count)


count = 10**9+1
board = [list(map(int, input().split())) for _ in range(10)]
papers = {1:5, 2:5, 3:5, 4:5, 5:5}
answer()