문제 링크
https://www.acmicpc.net/problem/1343
문제 유형
Greedy
🌈문제
민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB
이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.
폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.
출력
첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.
1. 아이디어
- 들어오는 리스트 값을 짝수 단위로 관찰.
- 거스름돈 문제와 매우 비슷하다고 생각함. 그렇기 때문에 가장 큰 단위 중심으로 잘라 생각하는 것이 맞을것이라고 확신
- 즉, 짝수를 기준으로 4로 나누어 떨어지는지 확인. 4로 나누어 떨어지면 바로 AAAA 배열로 바꾼다.
- 예외 처리에 대한 고민을 오랫동안 해서 푸는 데 시간이 오래 걸렸고, 새로운 tmp 리스트를 만들어 X값만 존재하는 것을 따로 빼 두려고 했는데 '.' 값도 출력해야 하는 관계로 해당 풀이과정은 오래 걸릴 것으로 판단하고 python의 list slice 기능을 이용하는 것이 더 낫다는 판단
2. 코드
board = input()
i=0
while True:
if i==len(board):
break
if board[i:i+4] =='XXXX':
i=i+4
board = board.replace('X','A',4)
elif board[i:i+2]=='XX':
i=i+2
board = board.replace('X','B',2)
elif board[i]=='.':
i=i+1
else:
board =-1
break
print(board)list의 slice 기능을 이용하면 쉽게 풀 수 있다.
