[BOJ] 17136 색종이 붙이기

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

1차 시도

처음에 색종이도 5가지에 5개씩 밖에 안 되고, 네모칸도 10 X 10이라서 해봐야 100 X 25 정도되겠다 싶어서 그리디로 풀려고 했다.

page = [input().split() for _ in range(10)]

papers = [0] * 6

for paper in range(5, 0, -1):
  for i in range(10 - paper + 1):
    for j in range(10 - paper + 1):
      if page[i][j] == '1':
        chk = False
        for x in range(0, paper):
          for y in range(0, paper):
            if page[i+x][j+y] != '1':
              chk = True
              break

          if chk:
            break

        if not chk:
          papers[paper]+=1
          for x in range(0, paper):
            for y in range(0, paper):
              page[i+x][j+y] = paper

chk = True
for i in range(5, 0, -1):

  if papers[1] > 5:
    print(-1)
    chk = False
    break

  rest = 0
  if papers[i] > 5:
    rest = papers[i] - 5
    papers[i] = 5

    if rest > 1:
      print(-1)
      chk = False
      break

    if i==5:
      papers[3]+=1
      papers[2]+=3
      papers[1]+=4
    elif i==4:
      papers[2] += 4
    elif i==3:
      papers[2] += 1
      papers[1] += 5
    elif i==2:
      papers[1] += 4

if chk:
  print(sum(papers))
  

그래서 첫 칸부터 큰 사이즈부터 비교하면서 되면 넣고 안 되면 작은 네모 넣는 방식을 썼고 마지막에 색종이 크기 부족하면 더 작은 종이로 나눠서 넣게하고 했는데 틀렸다. 강의를 들으니까 2 16크기의 네모가 있을 때 5 5 색종이하고 나머지 칸 채우는 것보다 4*4 색종이 2장 쓰는게 더 나은 경우가 있어서 그리디는 하면 안 된다고 했다.

강의 듣고 풀기

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

ans = 25

paper = [0] * 6


def is_possible(y, x, sz):
  if paper[sz] == 5:
    return False

  if y+sz > 10 or x+sz > 10:
    return False

  for i in range(sz):
    for j in range(sz):
      if board[y+i][x+j] == 0:
        return False

  return True

def mark(y, x, sz, v):
  for i in range(sz):
    for j in range(sz):
      board[y+i][x+j] = v

  if v:
    paper[sz]-=1
  else:
    paper[sz]+=1

def backtracking(y, x):
  global ans
  if y==10:
    ans = min(ans, sum(paper))
    return

  if x==10:
    backtracking(y+1, 0)
    return

  if board[y][x] == 0:
    backtracking(y, x+1)
    return

  for sz in range(1, 6):
    if is_possible(y, x, sz):
      mark(y, x, sz, 0)
      backtracking(y, x+1)
      mark(y, x, sz, 1) #원상복구

backtracking(0, 0)
print(-1 if ans == 25 else ans)'

백트래킹으로 접근했는데 작은 종이부터 넣어보면서 종이 크기 맞으면 일단 그거 넣고 다음 칸 가고 하는 방식이었다. 처음에 코드 따라치면서 이해가 안 됐는데 이거 쓰면서 이해가 되는 것 같다. 그래서 처음에 제일 작은 종이 집어넣어서 다 채워보고 안 되면 y, x = 0, 0인 시절로 돌아와서 더 큰 종이 넣고 비교해보고 하는 방식인 것 같다.
다음주 쯤에 다시 풀어봐야겠다.