[ BOJ 백준 17136번 - 색종이 붙이기 ] 해설 및 코드

백준 17136 - 색종이 붙이기

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

17136번: 색종이 붙이기

목적

1×1, 2×2, 3×3, 4×4, 5×5의 총 다섯 종류의 색종이를 이용하여, 10x10 크기의 종이에 1이 적힌 칸을 덮을 수 있는 색종이의 최소 개수를 구한다.

 

접근법

1. 완전탐색 알고리즘을 이용하여, 10x10 크기의 종이를 덮을 수 있는 모든 위치를 확인한다.

 

#include<iostream>
using namespace std;
int cnt[6]={0,5,5,5,5,5},result;
int B[10][10];
 
void fill(int i,int j,int k,int val){
    int rlen=i+k,clen=j+k;
    for(int r=i;r<rlen;++r)for(int c=j;c<clen;++c)B[r][c]=val;
}
 
bool canCover(int i,int j,int k){
    int rlen=i+k,clen=j+k;
    if(cnt[k]==0||rlen>10||clen>10)return false;
    for(int r=i;r<rlen;++r)for(int c=j;c<clen;++c)if(B[r][c]==0)return false;
    return true;
}
 
void foo(int i,int j){
    if(i==10){
        int tmp=25;
        for(int i=1;i<=5;++i)tmp-=cnt[i];
        if(result>tmp)result=tmp;
        return;
    }
    else if(j==10)foo(i+1,0);
    else if(B[i][j]==0)foo(i,j+1);
    else{
        for(int k=1;k<=5;++k)if(canCover(i,j,k)){
            fill(i,j,k,0);
            --cnt[k];
            foo(i,j+k);
            fill(i,j,k,1);
            ++cnt[k];
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    bool exist=false;
    for(int i=0;i<10;++i)for(int j=0;j<10;++j){
        cin>>B[i][j];
        exist|=(B[i][j]==1);
    }
    if(!exist)cout<<0;
    else{
        result=26;
        foo(0, 0);
        if(result==26)cout<<-1;
        else cout<<result;
    }
}