색종이 붙이기

백준 17136번: 색종이 붙이기

아이디어

색종이를 사이즈별로 붙이다가 더이상 붙일 수 없을 때 이전의 상태로 돌아가면 된다. 이 때 주의할 점이 몇가지 있다.

1. 색종이를 붙였을 때 10x10 사이즈 종이 바깥으로 벗어나는지 확인.
2. 같은 사이즈의 색종이는 5장까지 사용 가능하기 때문에 색종이가 남아있는지 확인.
3. 색종이를 붙일 공간이 있는 지 확인.

코드

#include <bits/stdc++.h>

using namespace std;

bool arr[10][10];
int paper[5] = {5, 5, 5, 5, 5};
int space = 0;
int MIN = INT_MAX;
vector<pair<int, int>> v;
vector<pair<int,int>>::iterator iter;

bool check_safe(int y, int x) {
    return y >= 0 && y < 10 && x >= 0 && x < 10;
}

void cover(int y, int x, int size, bool value) {
    for (int i = y; i < y+size; i++) {
        for (int j = x; j < x+size; j++) {
            arr[i][j] = value;
        }
    }
    if (value) { // uncover
        space += (size*size);
        paper[size-1] += 1;
    }
    else { // cover
        space -= (size*size);
        paper[size-1] -= 1;
    }
}

bool check(int y, int x, int size) {
    if (!check_safe(y+size-1, x+size-1)) return false;
    if (paper[size-1] <= 0) return false;
    for (int i = y; i < y+size; i++) {
        for (int j = x; j < x+size; j++) {
            if (arr[i][j] == 0) return false;
        }
    }
    return true;
}

void solve(int cnt) {
    if (space == 0) {
        MIN = min(MIN, cnt);
        return;
    }
    
    int y = (*iter).first;
    int x = (*iter).second;
    int idx = 0;
    while (!arr[y][x]) {
        iter++;
        idx++;
        y = (*iter).first;
        x = (*iter).second;
    }
    
    for (int i = 1; i <= 5; i++) {
        if (check(y, x, i)) {
            cover(y, x, i, 0);
            iter++;
            solve(cnt+1);
            cover(y, x, i, 1);
            iter--;                
        }
    }
    iter -= idx;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == true) {
                space++;
                v.push_back({i, j});
            }
        }
    }
    
    iter = v.begin();
    solve(0);
    
    if (MIN == INT_MAX) {
        if (space) cout << -1;
        else cout << 0;
    }
    else {
        cout << MIN;
    }
    
    return 0;
}

여담

iterator에서 정수를 빼서 이전 상태로 돌아갈 수 있다는 사실!