색종이 붙이기 (feat. 백준, 17136번)

색종이 붙이기
https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

 

반응형

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
using namespace std;
int ans, have_papers[6];
int arr[10][10];
bool check(register int x, register int y, register int c){
    if(x + c > 10 || y + c > 10 || have_papers[c] >= 5)
        return false;
    for(register int i = x, j; i < x + c; ++i)
        for(j = y; j < y + c; ++j)
            if(arr[i][j] != 1)
                return false;
    return true;
}
void attach(register int x, register int y, register int c){
    for(register int i = x, j; i < x + c; ++i)
        for(j = y; j < y + c; ++j)
            arr[i][j] = 0;
}
void detach(register int x, register int y, register int c){
    for(register int i = x, j; i < x + c; ++i)
        for(j = y; j < y + c; ++j)
            arr[i][j] = 1;
}
bool is_all_attach(){
    for(register int i = 0, j; i < 10; ++i)
        for(j = 0; j < 10; ++j)
            if(arr[i][j] == 1)
                return false;
    return true;
}
void dfs(register int x, register int y, register int count){
    while(arr[x][y] == 0)
        if(++y == 10){
            if(++x == 10){
                ans = min(ans, count);
                return;
            }
            y = 0;
        }
    if(ans <= count)
        return;
    for(register int c = 5; c >= 1; --c)
        if(check(x, y, c)){
            attach(x, y, c);
            ++have_papers[c];
            dfs(x, y, count + 1);
            detach(x, y, c);
            --have_papers[c];
        }
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    memset(have_papers, 0, sizeof(have_papers));
    for(register int i = 0, j; i < 10; ++i)
        for(j = 0; j < 10; ++j)
            cin >> arr[i][j];
    ans = 99999999;
    dfs(0, 0, 0);
    if(ans == 99999999)
        cout << -1;
    else
        cout << ans;
    return 0;
}
// *&)*@*

 

 

1. (1,1)부터 (10,10)까지 순차적으로 탐색하며 5개의 색종이부터 1개의 색종이까지 모든 경우에 대해서 구하는 방식입니다.
2. 단, 각각의 색종이는 총 5장이라는 제한사항이 있으므로 이 경우를 넘어가거나 이미 구한 색종이의 총 개수보다 더 큰 색종이가 필요한 경우를 제외시키면 됩니다.
3. 전형적인 dfs 문제입니다.