728x90
반응형
문제:
민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB
이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.
폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.
입력:
첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.
출력:
첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.
풀이방법:
X인 부분을 그리디하게 채워나가도록 한다. X가 4개이상이라면 AAAA로 채우고, 4개 미만이라면 BB로 채우도록 한다. 이 때, X가 남은 경우 혹은 X가 부족한 경우가 덮을 수 없는 케이스라고 판단한다.
|
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
|
string = input()
patterns = string.split('.')
answer = True
answer_pattern = []
for pattern in patterns:
if pattern =='':
continue
pattern_len = len(pattern)
tmp_pattern = ''
while pattern_len > 0:
if pattern_len>=4:
pattern_len-=4
tmp_pattern += 'AAAA'
elif pattern_len<4:
pattern_len-=2
tmp_pattern += 'BB'
if pattern_len<0:
answer_pattern = []
break
elif pattern_len==0:
answer_pattern.append(tmp_pattern)
answer = ''
idx = 0
next_ = True
if len(answer_pattern):
for s in string:
if s !='.' and next_:
answer+=answer_pattern[idx]
next_ = False
idx+=1
elif s =='.':
answer+='.'
next_ = True
print(answer)
else:
if set(string)=={'.'}:
print(string)
else:
print(-1)
|
cs |
문제링크:
https://www.acmicpc.net/problem/1343
1343번: 폴리오미노
첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.
www.acmicpc.net
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]Lv 2. 숫자 변환하기 (0) | 2023.07.11 |
|---|---|
| [BOJ] 2623. 음악프로그램 (0) | 2023.07.10 |
| [BOJ] 18405. 경쟁적 전염 (0) | 2023.07.06 |
| [Programmers]Lv 2. 택배상자 (0) | 2023.07.05 |
| [1138] 한 줄로 서기 (0) | 2023.07.04 |