백준 17136 색종이 붙이기

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

문제를 읽고 가장 먼저 들어온점은 일단 10x10배열이라 배열이 크지 않다는 점.

색종이 수를 가장 적게 써야하는데,
예제 5번을 보면 직관적으로는 여기다가 어떤것을 붙이고 저기다가는 어떤것을 붙이고가 눈에 보인다.
문제점은 이걸 어떻게 코드로 옮길까...

처음 생각해낸 아이디어는 일단 색종이를 가장 큰것부터 붙여보았다 떼었다가 다른것을 붙여보면서 가지치기 하는 것이다.
위의 생각은 백트래킹으로 구현할 수 있겠다고 생각했고, 이를 구현하였다.

큰 색종이부터 작은 색종이까지 붙여가며 상태를 넘겨가는 방식으로 구현했다.
만약 이전에 찾았던 최소의 색종이 수 보다 현재 색종이 수가 더 크다면 해당 경우는 가지치기를 해주었다.

arr = []
for i in range(10):
    arr.append(list(map(int,input().split())))
ans = 99
def check(x,y,n,array):
    if x + n > 10 or y + n > 10:
        return False
    for i in range(n):
        for j in range(n):
            if array[x+i][y+j]:
                continue
            else:
                return False
    return True

def toggle(x,y,n,array):
    for i in range(n):
        for j in range(n):
            array[x+i][y+j] ^= 1

def isfilled(array):
    ans = 0
    for row in array:
        ans += sum(row)
    if ans == 0:
        return True
    else:
        return False

def dfs(x,y,cnt,array):
    y %= 10
    if x >= 10:
        return
    global ans
    for c in cnt:
        if c > 5:
            return
    if array[x][y]:
        for k in range(5,0,-1):
            if cnt[k-1] > 5 or sum(cnt) >= ans:
                continue
            if check(x,y,k,array):
                toggle(x,y,k,array)
                cnt[k-1] += 1
                dfs(x,y+k,cnt,array)
                toggle(x,y,k,array)
                cnt[k-1] -= 1
    else:
        if y == 9:
            dfs(x+1,0,cnt,array)
        else:
            dfs(x,y+1,cnt,array)
    if isfilled(array):
        ans = min(ans,sum(cnt))

dfs(0,0,[0,0,0,0,0],arr)

if ans == 99:
    print(-1)
else:
    print(ans)