| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 12953 | 4758 | 2357 | 32.164% |
문제
<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.
색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.
종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.
입력
총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.
출력
모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.
접근
접근은 어렵지 않다. 그냥 모든 칸에 색종이를 붙여보면 된다.
백트래킹 방식으로 유망하지 않은 부분에서는 return을 붙여주면서, 브루트포스로 구하면 된다.
구현하는 것이 풀이 방식에 따라 코드 길이가 천차만별일 것 같다.
풀이
처음엔 vector<vector>를 함수 인자로 갖고 다닐까 생각했는데,
굳이 그럴 필요가 없을 것 같아 전역으로 선언했다.
remain을 parameter로 둬서 탈출문에 적용시켰다.
y, x 값에 대한 전처리도 간단하게 해주면 된다.
크기를 1 ~ 5까지 확인하면서, 색종이가 있으면 붙여준다.
재귀에 들어가기 전 값을 바꿔주고, 나올 때 값을 다시 바꿔주는 작업만 잘 수행하면 된다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int answer = 30, paper[5] = { 5, 5, 5, 5, 5 };
vector<vector<int>> arr(10);
int use_paper()
{
int ret = 25;
FUP(i, 0, 4) ret -= paper[i];
return ret;
}
void change(int y, int x, int len)
{
FUP(i, y, y + len)
{
FUP(j, x, x + len)
{
arr[i][j] ^= 1;
}
}
}
void solve(int y, int x, int remain)
{
if (remain == 0)
{
answer = min(answer, use_paper());
return;
}
if (x >= 10)
{
solve(y + 1, 0, remain);
return;
}
if (!arr[y][x]) solve(y, x + 1, remain);
FUP(len, 0, 4)
{
if (x + len >= 10 || y + len >= 10) break;
bool ok = true;
FUP(i, y, y + len)
{
if (!arr[i][x + len]) ok = false;
}
FUP(j, x, x + len)
{
if (!arr[y + len][j]) ok = false;
}
if (!ok) break;
if (!paper[len]) continue;
change(y, x, len);
paper[len]--;
solve(y, x + len + 1, remain - (len + 1) * (len + 1));
paper[len]++;
change(y, x, len);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int remain = 0;
FUP(i, 0, 9)
{
arr[i].resize(10);
FUP(j, 0, 9)
{
CIN(arr[i][j]);
remain += arr[i][j];
}
}
solve(0, 0, remain);
answer == 30 ? COUT(-1) : COUT(answer);
return 0;
}