백준 17136 색종이 붙이기 -python
문제풀이
- 색종이 붙이기 문제
- 왼쪽 모서리 부터 1,2,3,4,5크기의 색종이를 모두 하나씩 붙여본다
code
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
def f(n, s): # n 사용한 종이수, s 남은 1
global minV
if s==0:
if minV>n:
minV = n
elif n>=minV:
return
elif minV==4:
return
elif sum(paper)==0:
return
else:
for i in range(10):
for j in range(10):
if m[i][j]==1 and visited[i][j] ==0:
# 왼쪽 모서리로 가정
# 덮는 크기
for k in range(5, 0, -1):
# 종이가 남아있고
if paper[k]>0 and i+k<=10 and j+k<=10:
cover = 0
for r in range(i, i+k):
for c in range(j, j+k):
if visited[r][c]==0:
cover += m[r][c]
# 덮어지면
if cover==(k*k):
for r in range(i, i + k):
for c in range(j, j + k):
visited[r][c] = 1
paper[k] -= 1
f(n+1, s-k*k)
for r in range(i, i + k):
for c in range(j, j + k):
visited[r][c] = 0
paper[k] += 1
return
m = [list(map(int, input().split()))for _ in range(10)]
visited = [[0]*10 for _ in range(10)]
minV = 26
s = 0
paper = [0, 5, 5, 5, 5, 5]
for i in range(10):
for j in range(10):
if m[i][j]==1:
s += 1
f(0, s)
if minV == 26:
minV = -1
print(minV)
##
