Search

[백준 1343] 폴리오미노

[백준 1343] 폴리오미노

문제 요약

X를 A 또는 B로 바꿔서 보드판을 다시 출력하면 된다.
단, 다음 우선순위에 따라 폴리오미노로 변경 가능
1.
XXXX → AAAA
2.
XX → BB
그 외의 경우엔 불가
바꿀 수 없는 X가 있다면 -1를 출력하고 프로그램 종료

알고리즘 : 그리디

1.
XXXX가 있다면 먼저 AAAA로 바꾸고,
2.
남은 XX를 BB로 바꾸기

풀이 1

주어진 보드판 요소를 순서대로 하나하나씩 탐색하며 테스트
공통
카운트 변수 cnt를 선언하고 X가 등장할 때마다 +1
더불어 X를 일단 A로 다 바꿔주기
Case 1 : .이 등장할 경우
현재까지의 cnt를 체크
홀수 → 덮을 수 없는 경우이므로 -1 출력
XXX.XX
cnt를 4로 나눈 나머지가 2. 직전 마지막 X 두개는 BB로 덮어주기
XXXXXX.XX
cnt0으로 초기화
Case 2 : 마지막이 X로 끝나는 경우
ex) XXXXXX / XX..XX
cnt를 4로 나눈 나머지가 2 → 마지막 X 두개는 BB로 덮어주기

풀이 소스 코드

import sys si = sys.stdin.readline # 폴리오미노 함수 def polyomino(i): if cnt % 2 == 1: print(-1) exit(0) elif cnt % 4 == 2: board[i - 1] = 'B' board[i - 2] = 'B' # 리스트 형태로 보드판의 요소를 저장 board = list(map(str, si().rstrip())) cnt = 0 # 보드판 전체 탐색 for i in range(len(board)): if board[i] == 'X': # X가 나오면 일단 모두 A로 덮어주기 board[i] = 'A' cnt += 1 else: # .가 나올 경우 polyomino(i) cnt = 0 # 마지막이 X로 끝날 경우를 대비해 한번 더 폴리오미노 함수 실행 polyomino(0) for i in board: print(i, end = '')
Python

풀이 2

가능한 XXXX를 모두 AAAA로 먼저 바꾸고, 그 다음에 남은 XXBB로 바꾼다.
변환 후, 보드판에 남은 X가 있다면 -1, 없다면 폴리오미노로 덮은 보드판을 출력한다.

풀이 소스 코드

import sys si = sys.stdin.readline board = si().rstrip() board = board.replace('XXXX', 'AAAA') board = board.replace('XX', 'BB') if 'X' in board: print(-1) else: print(board)
Python

회고

2달 전에 한번 풀어보고 다시 풀어 본 문제다.
실버 5의 난이도와 정답률 52%로 객관적으로도 어려운 문제는 아니며, 간단한 풀이로 해결 가능이 가능하다.
하지만 처음도 그랬고 두번 째로 풀 때도 풀이 1으로 시도를 해서 해결이 쉽지 않았던.. 하지만 2달 전에는 풀이 1은 반례 처리를 못해서 실패했었지만, 이번에는 성공..!
결론은.. 최대한 간단하게 생각하면 답이 쉽게 나올 수 있다!