백준(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;

}