파이썬 그리디 알고리즘 백준 1343 폴리오미노

문제

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

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

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

입력

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

출력

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

풀이

사전순으로 가장 앞서는 답을 출력해야 하기 때문에 AAAA를 최대한 사용해야 한다.

우선 .은 폴리오미노로 덮으면 안되므로 입력값을 .로 split한다.

split한 리스트를 순회하여

길이가 4보다 크고, 2로 나누어진다면

길이를 4로 나눈 몫만큼 AAAA를 사용하고 그 나머지를 2로 나눈 몫만큼 BB를 사용한다.

길이가 4보다 작고 2로 나누어진다면

길이를 2로 나눈 몫만큼 BB를 사용한다.

두 경우를 제외하고 전체를 덮을 수 있는 경우가 없기 때문에 fail값을 True로 설정한다.

변환이 끝나고

fail이 True면 -1을 출력하고

True가 아니라면 마지막 인덱스 전까지는 .과 함께 출력하고 마지막인덱스는 그대로 출력한다.

 

import sys
sts = sys.stdin.readline().rstrip("\n")
splitSts = sts.split(".")
ans = []
fail=False
for splitSt in splitSts:
    if(len(splitSt)>=4 and len(splitSt)%2==0):
        splitSt = "AAAA"*(len(splitSt)//4) + "BB"*((len(splitSt)%4)//2)
        ans.append(splitSt)
    elif(len(splitSt)%2==0):
        splitSt = "BB"*(len(splitSt)//2)
        ans.append(splitSt)
    else:
        fail=True
        break

if(fail):
    print(-1)
else:
    for i in range(len(ans)):
        if(i==len(ans)-1):
            print(ans[i])
        else:
            print(ans[i],end=".")