https://www.acmicpc.net/problem/17136
17136번: 색종이 붙이기
<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. <그림 1> 색종이를 크
www.acmicpc.net
5, 4, 3, 2, 1로 일일이 다 해보기?
라고 생각하면
바로 반례를 만난다.
재귀로 풀어야 한다!
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int ans = 100;
int map[14][14];
int paper[5] = { 5, 5, 5, 5, 5 };
void fill(int row, int col, int k, int v)
{
for (int i = row; i <= row + k; i++)
{
for (int j = col; j <= col + k; j++)
{
map[i][j] = v;
}
}
}
bool bound(int row, int col, int k)
{
if (row + k >= 10 || col + k >= 10)
return false;
else
return true;
}
bool check(int row, int col, int k)
{
for (int i = row; i <= row + k; i++)
{
for (int j = col; j <= col + k; j++)
{
if (map[i][j] == 0)
return false;
}
}
return true;
}
bool full_check()
{
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
{
if (map[i][j] == 1)
return false;
}
}
return true;
}
void go(int cnt)
{
if (ans < cnt)
{
return;
}
if (full_check())
{
if (ans > cnt)
ans = cnt;
return;
}
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
{
if (map[i][j] == 1)
{
for (int k = 4; k >= 0; k--)
{
if (bound(i, j, k) && paper[k] > 0 && check(i, j, k))
{
paper[k]--;
fill(i, j, k, 0);
go(cnt + 1);
paper[k]++;
fill(i, j, k, 1);
}
}
// 맨 처음 1부터 재귀를 쭉 돌리면 더 이상 할 필요가 없다!
// 그러므로 return;
return;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
cin >> map[i][j];
}
go(0);
if (ans == 100)
cout << -1 << '\n';
else
cout << ans << '\n';
return 0;
}
|
cs |
paper[k]--;
fill(i, j, k, 0);
go(cnt + 1);
paper[k]++;
fill(i, j, k, 1);
치킨 배달부터 해서 신기한 소수
엄청 풀었던 브루트포스 재귀이다.
선택 / not 선택
if (ans < cnt)
{
return;
}
이건 안넣으면 정답은 되는데 시간이 20ms 차이난다.
ans 보다 크다면 굳이 필요가 없으므로
return; 해서 시간을 단축시키자
