백준(BOJ) 17136번 색종이 붙이기
문제: https://www.acmicpc.net/problem/17136
<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.
<그림 1>
색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.
종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.
나의 풀이:
완전탐색을 통하여 종이가 1인 구간을 발견했을 시 1*1 ~ 5*5 사이즈 까지의 색종이 들을 재귀함수로 하나씩 호출하면서 최소값을 찾아보자.
코드 ( C ++ )
#include <iostream>
#include <algorithm>
using namespace std;
int paper[10][10];
int cntPaper[5] = { 5,5,5,5,5 };
int ret, cnt;
const int INF = 987654321;
void solve(int y, int x, int cnt)
{
if (x == 10) {
solve(y + 1, 0, cnt );
return;
}
// ( 10 , 0 ) 에서 처리 될 것
if (y == 10) {
ret = min(ret, cnt);
return;
}
if (paper[y][x] == 0)
{
solve(y, x + 1, cnt);
return;
}
// n * n 정하기
for (int n = 1; n <= 5; ++n) {
// 색종이 다쓰거나 범위를 넘는 경우 제외
// 실제 덮는 값은 0,1,2,3,4 이니 y +n > 9 가 아닌 10 이여야한다.
if (cntPaper[n-1] == 0 || y + n > 10 || x + n > 10)
continue;
bool check = false;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
{
if (paper[y + i][x + j] == 0) {
check = true;
break;
}
}
if (check) break;
}
if (check) continue;
// n*n 색종이로 종이를 덮는다.
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
paper[y + i][x + j] = 0;
// n 색종이를 하나 사용했으니 cnt에 +1, 색종이개수는 1개 빼준다.
cnt++;
cntPaper[n-1]--;
solve(y, x + n, cnt);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
paper[y + i][x + j] = 1;
// 다음 번 이용할 색종이를 위해 원상복구 시켜준다.
cnt--;
cntPaper[n-1]++;
}
}
int main()
{
for (int i = 0; i < 10; ++i)
for (int j = 0; j < 10; ++j)
cin >> paper[i][j];
ret = INF;
solve(0,0, 0 );
if (ret == INF)
cout << -1 << "\n";
else
cout << ret << "\n";
return 0;
}
