백준 17136문제

#include <bits/stdc++.h>
using namespace std;

int paper[11][11];
int cnt[6] = {0,};
int ans = 1e9;

void update(int size, int x, int y, int num){
    for(int i = x ; i<x+size ; i++)
        for(int j = y ; j<y+size ; j++)
            paper[i][j] = num;
}

bool check(int size,int x, int y){
    if(x+size > 10 || y+size > 10) return false;
    for(int i = x ; i<x+size ; i++)
        for(int j = y ; j<y+size ; j++)
            if(!paper[i][j]) return false;
    return true;
}

void dfs(int x, int y, int count){

    bool flag = false;
    for(int i =x ;i<10 ; i++){
        for(int j =y ; j<10 ; j++){
            if(paper[i][j]){
                x = i, y = j,flag = true;
                break;
            } 
        }
        if(flag) break;
    }
    if(!flag){
        if(ans > count){
            ans = count;
        }
        return;
    }

    for(int i = 5 ; i>0 ; i--){
        if(cnt[i] == 5) continue;
        if(check(i,x,y)){
            cnt[i]++;
            update(i,x,y,0);
            dfs(x,y,count+1);
            cnt[i]--;
            update(i,x,y,1);
        }
    }
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);


    for(int i =0 ; i<10 ; i++)
        for(int j = 0 ; j<10 ; j++)
            cin >> paper[i][j];


    dfs(0,0,0);
    if(ans == 1e9) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}

백트래킹 문제 입니다.