[BOJ] 1343. 폴리오미노

문제:

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.

출력:

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

풀이방법:

X인 부분을 그리디하게 채워나가도록 한다. X가 4개이상이라면 AAAA로 채우고, 4개 미만이라면 BB로 채우도록 한다. 이 때, X가 남은 경우 혹은 X가 부족한 경우가 덮을 수 없는 케이스라고 판단한다.

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)

문제링크:

https://www.acmicpc.net/problem/1343

1343번: 폴리오미노