※ 본 문제는 백준 온라인 저지 사이트에서 발췌하였습니다.
민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB
이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.
폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.
첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.
첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.
# baekjoon
# 1343 폴리오미노
board = input()
for i in range(0, len(board)):
if 'XXXX' in board: # XXXX가 포함된 경우
board = board.replace('XXXX', 'AAAA') # replace 함수를 사용해서 바꿔줌
for i in range(0, len(board)):
if 'XX' in board: # XX가 포함된 경우
board = board.replace('XX', 'BB')
if 'X' in board: # 위에서도 걸러지지 못하고 X가 남을 경우
board = "-1" # -1 출력
print(board)
어떤것을 먼저 처리할지를 생각하면 쉽게 풀 수 있는 문제였다. greedy 문제의 대다수가 그렇지만 가장 먼저 처리해야할 부분들이 존재한다. 이 문제에서도 'AAAA'로 먼저 보드를 채우고 나머지 부분을 'BB'로 채운 후, 그래도 채워지지 않는다면 -1을 출력하게 하면서 문제를 풀 수 있었다.