[백준] 1343 폴리오미노 - Python

문제

1343번: 폴리오미노

1343번: 폴리오미노

이 문제는 그리디 알고리즘으로 해결할 수 있는 문제로 문제 아이디어는 다음과 같습니다.

폴리오미노 2개(AAAA, BB)를 무한대만큼 가지고 있을 때, 겹침없이 X를 모두 폴리오미노로 덮어야 합니다. AAAA는 BB의 배수이기 때문에 항상 최소한의 교체로 최적의 해를 가질 수 있습니다.

풀이 1 - Python

s = input()
idx = 0
answer = ''

while idx<len(s):
    if s[idx : idx + 4] == 'XXXX':
        answer+='AAAA'
        idx+=4
    elif s[idx : idx + 2] == 'XX':
        answer += 'BB'
        idx+=2
    elif s[idx] == 'X':
        answer = str(-1)
        break
    else:
        answer += s[idx]
        idx+=1
print(answer)

풀이 2 - Python

board = input()

board = board.replace('XXXX', 'AAAA')
board = board.replace('XX', 'BB')

if 'X' in board:
    print(-1)
else:
    print(board)

• 위 코드는 XXXX를 AAAA로 XX는 BB로 치환해줍니다.
• 이 후, 바뀌지 않은 문자 X가 있으면, 폴리오미노로 덮을 수 없는 경우이므로 -1을 출력해줍니다.
• 파이썬의 replace(a,b) 메소드 : “a를 b로 바꾸어라”를 의미합니다.