[백준] 1342 폴리오미노

문제

• AAAA와 BB라는 폴리오미노 2개가 무한개 있다.
• '.' 과 'X'로 이루어진 보드판이 주어졌을 때 겹침없이 'X'를 모두 폴리오미노로 덮을 경우의 보드판 출력하기
• 경우의 수가 여러 개면 사전순으로 가장 앞서는 답을 출력하고 덮을 수 없으면 -1을 출력한다.

 

풀이

• 예외 처리 : '.'로 분리했을 때 XXX의 그룹이 홀수 길이면 보드를 채울 수 없다.
• '.' 이전까지 그룹화 했을 때 XX인 경우 BB로 바꾸고, XXXX..XX인 경우 적절히 보드를 채워준다.
• 마지막 그룹을 채워준다.

 

string = input()
# 예외 처리
for s in string.split('.') :
    if len(s) % 2 == 1 :
        print("-1")
        exit()

prev = 0
answer = ''
for i, s in enumerate(string):
    if s == '.' :
        if i-prev == 2 :		# XX인 경우
            answer += "BB"
        else :					# XXXX..XX인 경우
            answer += "AAAA" * ((i-prev) // 4) + "B" * ((i-prev)%4)
        answer += '.'
        prev = i+1

# 마지막 그룹 확인
n = len(string)
if prev < n and string[prev] == 'X' and string[-1] == 'X' :
    answer += "AAAA" * ((n-prev) // 4) + "B" * ((n-prev)%4)

print(answer)

 

References

• 백준 그리디