[백준/1053] 팰린드롬 공장 (Python)

Problem : https://www.acmicpc.net/problem/1053

1053번: 팰린드롬 공장

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:18:07

 

---

 

문제 설명

 

 

팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다.

모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다.

 

1. 문자열의 어떤 위치에 어떤 문자를 삽입 (시작과 끝도 가능)
2. 어떤 위치에 있는 문자를 삭제
3. 어떤 위치에 있는 문자를 교환
4. 서로 다른 문자를 교환

 

1, 2, 3번 연산은 마음껏 사용할 수 있지만, 마지막 연산은 많아야 한 번 사용할 수 있다.

문자열이 주어졌을 때, 팰린드롬으로 만들기 위해 필요한 연산의 최솟값을 출력하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 문자열이 주어진다. 영어 소문자로만 이루어져 있고, 길이는 최대 50이다.

 

출력

 

첫째 줄에 문제의 정답을 출력한다.

 

입력 예시

babacvabba

 

출력 예시

 

2

 

 

---

 

풀이

 

DP 문제 + 브루트포스 문제.

 

세 가지 연산을 어떻게 적용시켜볼까 생각하지말고, 문제를 단순화시켜 접근할 필요가 있다.

 

DP[i][j]를 1~i-1, j+1~string이 펠린드롬을 만족시킬 때의 경우의 수라고 가정하자. 저 세 가지 연산은 사실

• i번째와 j번째 문자열이 같다면 i+1, j-1을 바로 탐색(어떤 연산도 수행할 필요 없음. 이전 문자열들은 팰린드롬임이 조건상 충족됨)
• 그렇지 않다면
  • i번째와 j-1번째 : 이 때는 i번째에 맞추어 j번째 원소를 삭제, 혹은 j번째에 맞추어 i번째 원소를 j와 동일한 원소로 삽입하는 경우와 같다.
  • i+1번째와 j번째 : 위와 반대로 적용된다.
  • i+1번째와 j-1번째 : 이 경우는 i번째 혹은 j번째에 맞추어 다른 원소를 교환하는 경우와 같다.
  • 이 모든 경우가 비용 1이 소모된다는 점을 고려하여 탐색을 진행할 수 있다.
• i >= j라면 해를 업데이트하고 지금의 탐색을 중지한다.

로 요약해볼 수 있다. 최적해가 모든 부분 최적해를 만족하는 구조이므로 부분 최적회를 갱신하지 못하는 경우에 역시 탐색을 중단할 수 있다.

 

문제는 4번인데, 생각해보면 4번의 모든 경우의 수는 O(N^2)이 되며, N <= 50이므로 충분히 브루트포스로 도전해 볼 수 있겠다. 이 때의 각 후보값은 (DP 연산을 통해 구해진 값 + 1)이 된다. 모든 과정을 종료한 후 구한 최종 값을 출력하면 풀이 완료.

 

 

풀이 코드

from collections import deque
MAX = float('inf')
di = [0, 1, 1]
dj = [-1, 0, -1]

string = list(input().strip())

def cal_dp(target) :
  result = MAX
  dp = [[MAX]*len(string) for _ in range(len(string))]
  dp[0][-1] = 0
  q = deque([(0, len(string)-1, 0)])

  while q :
    i, j, dist = q.popleft()
    if i >= j :
      result = min(result, dist)
      continue
    if target[i] == target[j] :
      if dp[i+1][j-1] > dist :
        dp[i+1][j-1] = dist
        q.append((i+1, j-1, dist))
      continue
    for k in range(3) :
      ai, aj = i + di[k], j + dj[k]
      if dp[ai][aj] > dist + 1 :
        dp[ai][aj] = dist + 1
        q.append((ai, aj, dist+1))

  return result

answer = cal_dp(string)
for i in range(len(string)-1) :
  for j in range(i+1, len(string)) :
    if string[i] == string[j] :
      continue
    string[i], string[j] = string[j], string[i]
    answer = min(answer, cal_dp(string)+1)
    string[i], string[j] = string[j], string[i]

print(answer)

풀이 완료!