이번 문제는 백트레킹을 통해 해결하였다. 조금 복잡한 백트레킹이었는데, 우선 함수의 인자로 y, x를 받는다. 이는 좌표를 의미하고, 좌표를 오른쪽으로 이동시키면서 끝에 도달하면 아래로 한칸 내리는 식으로 진행하였다. 현재 좌표 값이 1이라면 1~5에 해당하는 색종이 크기만큼을 확인하고, 사이즈가 맞는 경우에만 해당 좌표들을 0으로 바꿔주고 재귀호출하고, 다시 값을 원래대로 돌려놓는 방식으로 진행하였고, 이 과정에서 현재 선택한 색종이의 총 갯수가 5개가 넘지 않도록 하였다. 재귀호출을 할 때에는 선택한 색종이의 크기+1만큼을 x좌표에 더하여 진행해주고, 현재 좌표값이 0일 경우에는 x좌표를 1만 더 크게하여 다음 재귀호출을 진행하였다. 이 과정에서 y가 10 이상이 되면 결과 변수의 최솟값을 구하도록 하였고, 최종 결과 변수가 1e9일 경우, -1로 갱신해주었다.

Code

grid = [list(map(int, input().split())) for _ in range(10)]
cnts = [0 for _ in range(5)]
answer = 1e9
def chk(y, x, sz):
    for i in range(y, y+sz+1):
        for j in range(x, x+sz+1):
            if grid[i][j] == 0:
                return False
    return True
def find_min(y, x):
    global answer
    if y >= 10:
        answer = min(answer, sum(cnts))
        return
    if x >= 10:
        find_min(y+1, 0)
        return
    if grid[y][x] == 1:
        for sz in range(5):
            if cnts[sz] >= 5:
                continue
            if not (0 <= y + sz < 10 and 0 <= x + sz < 10):
                continue
            if chk(y, x, sz):
                for i in range(y, y+sz+1):
                    for j in range(x, x+sz+1):
                        grid[i][j] = 0
                cnts[sz] += 1
                find_min(y, x+sz+1)
                cnts[sz] -= 1
                for i in range(y, y+sz+1):
                    for j in range(x, x+sz+1):
                        grid[i][j] = 1
    else:
        find_min(y, x+1)
find_min(0, 0)
if answer == 1e9:
    answer = -1
print(answer)