백준 17136 색종이 붙이기 풀이

문제

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

&Title
17136번 - 색종이 붙이기

&Question
<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 
색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 
총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 
있다.<그림 1>색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 
1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 
1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 
한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 
겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 
0이 적힌 칸에는 색종이가 있으면 안 된다.종이가 주어졌을 때, 
1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 
구해보자. 

&Input
총 10개의 줄에 종이의 각 칸에 적힌 수가 
주어진다. 

&Output
모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 
1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다. 

&Example
-input
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

-output
0

-input
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

-output
4

-input
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

-output
5

-input
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

-output
-1

-input
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

-output
7

-input
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

-output
4

-input
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1

-output
6

-input
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 1 1 0 0 0
0 1 1 1 0 1 1 0 0 0
0 1 1 1 0 0 0 0 0 1

-output
5

접근

• 색종이를 큰거부터 작은것 순으로 붙여나가준다.(최솟값 갱신에 더 효율적임)

풀이

1. y==10 인경우 완전탐색이 끝난것이므로 최솟값을 갱신해준다. (이때 전부 0으로 갱신되었나 확인 할 필요는 없다. 완전탐색이후 0으로 채우지 못하는 경우는 재귀로 더이상 돌지 않기 때문이다.)
2. 기저조건들로 예외 처리를 해준다.

    if (cnt > res)return;
    if (x == 10) {
        dfs(y + 1, 0, cnt);
        return;
    }
    if (map[y][x] == 0) {
        dfs(y, x + 1, cnt);
    }
   

3. 큰 사이즈의 색종이부터 붙일 수 있는 경우 붙여나가며 재귀를 돌린다.

소스

#include <iostream>
#include <algorithm>
using namespace std;

int map[10][10];
int paper[6] = { 0, 5, 5, 5, 5, 5 };
int res = 1e9;

void dfs(int y, int x, int cnt) {
	// 기저 조건 : 결과보다 작으면 갱신할 가치가 없음
	if (cnt > res)return;
	// 81까지 끝까지 돌았으니 최솟값 갱신
	if (y == 10) {
		res = min(res, cnt);
		return;
	}
	// x좌표 넘어가면 다음줄로 넘겨줌
	if (x == 10) {
		dfs(y + 1, 0, cnt);
		return;
	}
	// 값 0이면 넘어감
	if (map[y][x] == 0) {
		dfs(y, x + 1, cnt);
	}

	// 크기 5~1까지 가능한 경우 재귀 돌려줌(큰거부터 해야 최솟값 갱신에 더 효율적
	for (int sz = 5; sz >= 1; --sz) {
		if (y + sz > 10 || x + sz > 10 || paper[sz] == 0)continue;

		bool flag = true;
		// 색종이를 붙일 수 있는지 확인
		for (int i = y; i < y + sz; ++i) {
			for (int j = x; j < x + sz; ++j)
				if (map[i][j] == 0) {
					flag = false;
					break;
				}
			if (!flag)break;
		}
		if (!flag)continue;
		// 색종이를 붙여줌
		for (int i = y; i < y + sz; ++i)
			for (int j = x; j < x + sz; ++j)
				map[i][j] = 0;
		paper[sz]--;
		dfs(y, x + sz, cnt + 1);
		// 색종이를 뗌
		for (int i = y; i < y + sz; ++i)
			for (int j = x; j < x + sz; ++j)
				map[i][j] = 1;
		paper[sz]++;
	}
}


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

	for (int i = 0; i < 10; ++i)
		for (int j = 0; j < 10; ++j)
			cin >> map[i][j];
	dfs(0, 0, 0);
	if (res == 1e9)res = -1;
	cout << res << endl;
	return 0;
}