Greedy_BOJ #1343: 폴리오미노

https://www.acmicpc.net/problem/1343

문제

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

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

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

입력

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

출력

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

 

 

---

그리디 알고리즘이 잘 작동하는 문제들은 Greedy Choice Property를 갖고 있는 Optimal Structure인 문제들이다.

Greedy Choice Property란 앞의 선택이 이후 선택에 영향을 주지 않는 것이다.

Optimal Structure이란 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말한다.

 

그리디는 다이나믹 프로그래밍과 차이점이 Optimal Structure(최적 부분 구조)문제를 푼다는 것이다.

다이나믹 프로그래밍은 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션에 대한 선택을 한다.

그리디는 각 단계마다 로컬 최적해를 찾은 다음, 문제를 더 작게 줄여나가는 형태이다.

이 두 알고리즘의 접근 방향은 서로 반대의 구조임을 알 수 있다.

 

---

# Sol1

폴리오미노 2개(AAAA, BB)를 무한개만큼 갖고 있는 상황

입력받은 보드판을 순서대로 읽는다

'XXXX'가 있으면 우선적으로 AAAA를 추가,

'XX'가 있다면 BB로 추가한다.

'X'가 있다면 break로 빠져나간다.

최종적으로 입력받은 board의 len과 result의 len이 같다면 result를 출력하고, 같지 않다면 -1를 출력한다.

 

import sys
def input():
  return sys.stdin.readline().rstrip()

board = input()
idx = 0
answer = []

while idx < len(board):
  if board[idx:idx+4] == 'XXXX':
    answer.append('AAAA')
    idx += 4
  elif board[idx:idx+2] == 'XX':
    answer.append('BB')
    idx += 2
  elif board[idx] == '.':
    answer.append('.')
    idx += 1
  else:
    break

answer = ''.join(answer)
if len(board) == len(answer):
  print(answer)
else:
  print(-1)

 

 

# Sol2

파이썬의 replace() 함수는 문자열 왼쪽부터 해당하는 문자열을 치환해 주는 함수이다.

import sys
def input():
  return sys.stdin.readline().rstrip()

board = input()

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

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