고정 헤더 영역
상세 컨텐츠
본문
https://www.acmicpc.net/problem/17136
17136번: 색종이 붙이기
<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. <그림 1> 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐
www.acmicpc.net
내 풀이:
|
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
125
126
127
128
129
|
field_original = [list(map(int, input().split())) for _ in range(10)]
result = 26
def pasting(i, j, count, field, use):
global result
try:
if i == 9 and j == 9:
if field[i][j] == 1:
count += 1
if result > count:
result = count
return
if count > result:
return
if field[i][j] == 0:
if j != 9:
pasting(i, j + 1, count, field, use)
elif i != 9:
pasting(i + 1, 0, count, field, use)
else:
TF1 = False
TF2 = False
TF3 = False
TF4 = False
if max(i, j) <= 8:
TF1 = True
for _ in range(1):
if field[i+_][j+1] == 0:
TF1 = False
break
for _ in range(2):
if field[i+1][j+_] == 0:
TF1 = False
break
if TF1 and max(i, j) <= 7:
TF2 = True
for _ in range(2):
if field[i + _][j + 2] == 0:
TF2 = False
break
for _ in range(3):
if field[i + 2][j + _] == 0:
TF2 = False
break
if TF2 and max(i, j) <= 6:
TF3 = True
for _ in range(3):
if field[i + _][j + 3] == 0:
TF3 = False
break
for _ in range(4):
if field[i + 3][j + _] == 0:
TF3 = False
break
if TF3 and max(i, j) <= 5:
TF4 = True
for _ in range(4):
if field[i + _][j + 4] == 0:
TF4 = False
break
for _ in range(5):
if field[i + 4][j + _] == 0:
TF4 = False
break
new_use = use[:]
if TF4 and new_use[4] <= 4:
new_field = [line[:] for line in field]
for _ in range(5):
for __ in range(5):
new_field[i+_][j+__] = 0
new_use[4] += 1
pasting(i, j + 1, count + 1, new_field, new_use)
new_use[4] -= 1
if TF3 and new_use[3] <= 4:
new_field = [line[:] for line in field]
for _ in range(4):
for __ in range(4):
new_field[i+_][j+__] = 0
new_use[3] += 1
pasting(i, j + 1, count + 1, new_field, new_use)
new_use[3] -= 1
if TF2 and new_use[2] <= 4:
new_field = [line[:] for line in field]
for _ in range(3):
for __ in range(3):
new_field[i+_][j+__] = 0
new_use[2] += 1
pasting(i, j + 1, count + 1, new_field, new_use)
new_use[2] -= 1
if TF1 and new_use[1] <= 4:
new_field = [line[:] for line in field]
for _ in range(2):
for __ in range(2):
new_field[i+_][j+__] = 0
new_use[1] += 1
pasting(i, j + 1, count+1, new_field, new_use)
new_use[1] -= 1
if new_use[0] <= 4:
new_field = [line[:] for line in field]
new_field[i][j] = 0
new_use[0] += 1
if j != 9:
pasting(i, j + 1, count + 1, new_field, new_use)
elif i != 9:
pasting(i + 1, 0, count + 1, new_field, new_use)
new_use[0] -= 1
except:
return
pasting(0, 0, 0, field_original, [0,0,0,0,0])
if result == 26:
print("-1")
else:
print(result)
|
Python3, 샘플은 맞았으나 오답
|
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
125
|
field_original = [list(map(int, input().split())) for _ in range(10)]
result = 26
def pasting(i, j, count, field, use):
global result
if i == 9 and j == 9:
if field[i][j] == 1:
count += 1
if use[0] == 5:
return
if result > count:
result = count
return
if count == result:
return
if field[i][j] == 0:
if j != 9:
pasting(i, j + 1, count, field, use)
elif i != 9:
pasting(i + 1, 0, count, field, use)
else:
TF1 = False
TF2 = False
TF3 = False
TF4 = False
if max(i, j) <= 8:
TF1 = True
for _ in range(1):
if field[i+_][j+1] == 0:
TF1 = False
break
for _ in range(2):
if field[i+1][j+_] == 0:
TF1 = False
break
if TF1 and max(i, j) <= 7:
TF2 = True
for _ in range(2):
if field[i + _][j + 2] == 0:
TF2 = False
break
for _ in range(3):
if field[i + 2][j + _] == 0:
TF2 = False
break
if TF2 and max(i, j) <= 6:
TF3 = True
for _ in range(3):
if field[i + _][j + 3] == 0:
TF3 = False
break
for _ in range(4):
if field[i + 3][j + _] == 0:
TF3 = False
break
if TF3 and max(i, j) <= 5:
TF4 = True
for _ in range(4):
if field[i + _][j + 4] == 0:
TF4 = False
break
for _ in range(5):
if field[i + 4][j + _] == 0:
TF4 = False
break
new_use = use[:]
if TF4 and new_use[4] <= 4:
new_field = [line[:] for line in field]
for _ in range(5):
for __ in range(5):
new_field[i+_][j+__] = 0
new_use[4] += 1
pasting(i, j + 1, count + 1, new_field, new_use)
new_use[4] -= 1
if TF3 and new_use[3] <= 4:
new_field = [line[:] for line in field]
for _ in range(4):
for __ in range(4):
new_field[i+_][j+__] = 0
new_use[3] += 1
pasting(i, j + 1, count + 1, new_field, new_use)
new_use[3] -= 1
if TF2 and new_use[2] <= 4:
new_field = [line[:] for line in field]
for _ in range(3):
for __ in range(3):
new_field[i+_][j+__] = 0
new_use[2] += 1
pasting(i, j + 1, count + 1, new_field, new_use)
new_use[2] -= 1
if TF1 and new_use[1] <= 4:
new_field = [line[:] for line in field]
for _ in range(2):
for __ in range(2):
new_field[i+_][j+__] = 0
new_use[1] += 1
pasting(i, j + 1, count+1, new_field, new_use)
new_use[1] -= 1
if new_use[0] <= 4:
new_field = [line[:] for line in field]
new_field[i][j] = 0
new_use[0] += 1
if j != 9:
pasting(i, j + 1, count + 1, new_field, new_use)
elif i != 9:
pasting(i + 1, 0, count + 1, new_field, new_use)
new_use[0] -= 1
pasting(0, 0, 0, field_original, [0,0,0,0,0])
if result == 26:
print("-1")
else:
print(result)
|
Python3, 1424ms
(9, 9)를 마지막으로 확인할 때 색종이를 붙여야 하는 구역이면 count만 1 올려주고 답을 출력했었는데 이때 이미 1*1짜리 색종이를 5장 사용한 상태라면 조건에 부합하기 때문에 이 과정을 생략하여 오답이 나왔었다.
'Python > 문제풀이 (삼성 A형 대비)' 카테고리의 다른 글
| 파이썬으로 풀어보는 백준 17822번: 원판 돌리기 (삼성 A형 기출 문제) (0) | 2020.02.07 |
|---|---|
| 파이썬으로 풀어보는 백준 16236번: 아기 상어 (삼성 A형 기출 문제) (0) | 2020.02.07 |
| 파이썬으로 풀어보는 백준 17135번: 캐슬 디펜스 (삼성 A형 기출 문제) (0) | 2020.01.27 |
| 파이썬으로 풀어보는 백준 16637번: 괄호 추가하기 (삼성 A형 기출 문제) (2) | 2020.01.26 |
| 파이썬으로 풀어보는 백준 17471번: 게리맨더링 (삼성 A형 기출 문제) (0) | 2020.01.23 |
댓글 영역