[백준] 17136번 - 색종이 붙이기

문제

💡

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력

출력

풀이

코드

#include <iostream>
#include <vector>
#include <sstream>
using namespace std;

int type[5] = { 5, 5, 5, 5, 5 };
bool paper[10][10];
int result = 23; // 최대값

// 좌표를 입력받고, 종이를 붙일 수 있는곳이 있는지 확인
bool check(int x, int y, int size) {
    if (x + size > 10 || y + size > 10) {
        return false;
    }

    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            if (!paper[i + x][j + y]) {
                return false;
            }
        }
    }

    return true;
}

void attach(int x, int y, int size, bool value) {
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            paper[i + x][j + y] = value;
        }
    }
}

void recursive(int x, int y, int count) {
    if (x >= 10) {
        result = min(result, count);
        return;
    }

    if (y >= 10) {
        recursive(x + 1, 0, count);
        return;
    }

    if (!paper[x][y]) {
        recursive(x, y + 1, count);
        return;
    }

    for (int i = 5; i > 0; --i) {
        if (type[i - 1] > 0 && check(x, y, i)) {
            type[i - 1]--;
            attach(x, y, i, false);
            // 다음 재귀 실행
            recursive(x, y, count + 1);
            type[i - 1]++;
            attach(x, y, i, true);
        }
    }
}
int main() {
    bool n;
    // 배열 입력
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < 10; ++j) {
            cin >> n;
            paper[i][j] = n;
        }
    }

    recursive(0, 0, 0);
    // 최소값 검사
    if (result == 23) {
        cout << -1;
    } else {
        cout << result;
    }

    return 0;
}

풀면서 알게 된 사실

// 논리적으로는 두 코드의 순서가 바뀌어도 상관이 없을텐데 이유는 모르겠지만
type[i - 1]--; // 이 코드가 위에 있을 때 시간이 더 적게 소요되었다.
attach(x, y, i, 0);
// 그리고 배열의