문제 링크
www.acmicpc.net/problem/17136
17136번: 색종이 붙이기
<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. <그림 1> 색종이를 크
www.acmicpc.net
접근 방법
DFS로 접근하여 풀 수 있는 문제였으나 시간 초과를 해결하는 과정이 관건이었던 문제였다.
전체 공간인 map[10][10]을 탐색하면서 색종이를 붙여야 되는 공간이 있다면 큰 색종이 부터 시작하여 붙일 수 있는지에 대한 여부를 확인하고 색종이를 붙인다. 완전탐색으로 가장 적은 색종이를 사용하는 경우의 값을 구하면 된다.
시간초과를 해결하는 방법을 떠올리기가 쉽지가 않았는데 핵심은 현재 공간에 어떤 색종이도 만족하지 않는다면 그 다음 과정에서 이러한 공간을 어차피 만족시킬 수 없다는 것이다. 즉 현재 공간을 만족시킬 수 없다면 다음 과정으로 진행을 시키지 않는 것이 시간초과를 해결하는 핵심이었다.
int solve(int x, int y, int cnt) {
if (complete())
return cnt;
if (mincnt <= cnt)
return mincnt;
for (int i = x; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (map[i][j] == 1) {
for (int size = 5; size >= 1; size--) {
if (inRange(i, j, size)) {
if (check_map(i, j, size) && cntPerSize[size] > 0) {
cntPerSize[size]--;
update_map(i, j, size, 0);
mincnt = min(solve(i, j, cnt + 1), mincnt);
cntPerSize[size]++;
update_map(i, j, size, 1);
}
}
}
return mincnt; // !!!중요: 위의 과정에서 만족하지 않는다면 return시킴
}
}
}
return mincnt;
}
소스 코드
#include <iostream>
#include <algorithm>
using namespace std;
int map[10][10];
int cntPerSize[6] = { 0,5,5,5,5,5 };
int mincnt = 99999;
bool inRange(int x, int y, int size) {
return (x + size - 1 < 10 && y + size - 1 < 10) ? true : false;
}
void update_map(int x, int y, int size, int action) {
for (int i = x; i < x + size; i++)
for (int j = y; j < y + size; j++)
map[i][j] = action;
}
bool check_map(int x, int y, int size) {
for (int i = x; i < x + size; i++)
for (int j = y; j < y + size; j++)
if (map[i][j] == 0)
return false;
return true;
}
bool complete() {
for (int i = 0; i < 10; i++)
for (int j = 0; j < 10; j++)
if (map[i][j] == 1)
return false;
return true;
}
int solve(int x, int y, int cnt) {
if (complete())
return cnt;
if (mincnt <= cnt)
return mincnt;
for (int i = x; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (map[i][j] == 1) {
for (int size = 5; size >= 1; size--) {
if (inRange(i, j, size)) {
if (check_map(i, j, size) && cntPerSize[size] > 0) {
cntPerSize[size]--;
update_map(i, j, size, 0);
mincnt = min(solve(i, j, cnt + 1), mincnt);
cntPerSize[size]++;
update_map(i, j, size, 1);
}
}
}
return mincnt;
}
}
}
return mincnt;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for (int i = 0; i < 10; i++)
for (int j = 0; j < 10; j++)
cin >> map[i][j];
int ans = solve(0,0,0);
if (ans < 99999)
cout << ans;
else
cout << -1;
}
개발 환경 : VS2017
질문, 지적 환영합니다!
'알고리즘 > 백준' 카테고리의 다른 글
| [C++] 백준 17406 배열돌리기4 (0) | 2021.01.03 |
|---|---|
| [C++] 백준 3190 뱀 (0) | 2021.01.03 |
| [C++] 백준 9470 Strahler 순서 (0) | 2020.09.25 |
| [C++] 백준 17070 파이프 옮기기 1 (0) | 2020.09.18 |
| [C++] 백준 17135 캐슬디펜스 (0) | 2020.09.18 |
