17136. 색종이 붙이기

시간 제한	메모리 제한
1초	512MB

문제

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

코드

maps = [list(map(int, input().split())) for _ in range(10)]

def check (x,y,scope) :
  if x + scope >= 10 or y + scope >= 10 :
    return False
  
  for i in range(scope + 1) :
    for j in range(i + 1) :
      if maps[x+i][y+j] != 1 or maps[x+j][y+i] != 1 :
        return False
  return True

answer = 26
paper = [5,5,5,5,5]

def use (x,y,scope, num) :
  for i in range(scope+1) :
    for j in range(scope+1) :
      maps[x+i][y+j] = num
  paper[scope] += -1 if num == 0 else 1

def solve (x,y) :
  global answer
  if y >= 10 : x, y = x+1, 0
  if x >= 10 :
    answer = min(answer, 25 - sum(paper))
    return
  if maps[x][y] == 0 :
    solve(x,y+1)
  else :
    for i in range(0,5) :
      if paper[i] > 0:
        if check(x,y,i) :
          use(x,y,i,0)
          solve(x,y+1)
          use(x,y,i,1)
        else :
          break
solve(0,0)
print(-1) if answer == 26 else print(answer)