[백준 1053번] 팰린드롬 공장 (Python3)

from itertools import *

def DFS(start,end,DP):
  for i,j in [(1,0),(0,1),(1,1)]:
    if DP[start+i][end-j]==N:
      DFS(start+i,end-j,DP)
    DP[start][end] = min(DP[start][end],DP[start+i][end-j]+int(not(i and j and seq[start]==seq[end])))

def palin():
  if N==1:
    return 0
  DP = [[N*int(i<j) for j in range(N)] for i in range(N)]
  DFS(0,N-1,DP)
  return DP[0][-1]

seq = [*input()]; N = len(seq)

result = palin()
for i,j in combinations(range(N),2):
  seq[i],seq[j] = seq[j],seq[i]
  result = min(result,palin()+1)
  seq[i],seq[j] = seq[j],seq[i]
print(result)

브루트 포스 + DP로 해결하였다.

4번 조건이 까다로웠다. 하지만 길이가 최대 50밖에 되지 않는다는 점을 이용해 브루트 포스로 해결할 수 있었다.

 

풀이를 설명하면,

1. DP[start][end]는 start~end 사이를 팰린드롬으로 만들기 위해서 필요한 연산의 가짓수이다.

2. 1번 연산과 2번 연산은 동일하게 취급할 수 있다. 1번과 2번 연산은 왼쪽과 오른쪽 중 하나를 삭제한다고 생각하면 되고, 3번 연산은 양쪽 다 삭제한다고 생각하면 된다.

3. 4번 연산은 브루트 포스로 해결한다. itertools.combinations를 이용해 모든 경우의 수에 대해 i,j 문자를 바꿔보고 그때의 최솟값을 구한다.

4. DFS+DP를 이용해서 최솟값을 구하고, 4번연산을 안했을때 최솟값과 4번연산을 했을때 최솟값+1 중 더 작은 값을 출력한다.

 

4번연산에서 시간복잡도 O(N^2), DP+DFS에서 시간복잡도 O(N^2)로 총 시간복잡도는 O(N^4)이다.

 

 

오늘의 교훈) N=1 또는 0일때 index 에러 조심