팰린드롬 만들기

문제

팰린드롬이란, 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 예를 들어, “abcba”, “abccba” 등이 있을 수 있다. 문자열이 주어질 때, 이를 팰린드롬으로 만들기 위하여 추가해야 하는 최소의 문자 개수를 출력하는 프로그램을 작성하시오. 예를 들어, 문자열이 “abca” 로 주어질 경우, ‘b’만 추가하면 “abcba” 를 만들 수 있으므로, 이 때는 1개의 문자만 추가하면 된다. 또 다른 예로써, 문자열이 “adcba” 로 주어질 경우에는, 문자 2개를 추가해야 한다.

 

입력

첫 번째 줄에 문자열이 주어진다. 이 문자열의 길이는 1,000 을 넘지 않는다.  

출력

주어진 문자열을 팰린드롬으로 만들기 위해서 추가해야 하는 문자 개수의 최솟값을 출력한다.

 

예제 입력

adcba

예제 출력

2

 

예제 입력

abccbdbac

예제 출력

3

 

#접근법

str = adcba 를 예로들고

dp_table을 정의해보면 dp_table(i, j)=i~j까지 문자열을 팰린드롬으로 만들기 위하여 추가해야 하는 문자 개수의 최솟값.

 

이를 좀 더 설명 해보자면

 [a, a] -> a에서 a까지 팰린드롬을 만들기 위해 추가해야하는 문자 개수의 최솟값은 0 이다. 즉(0,0)의 값은 0

 [d, c] -> d에서 c까지 팰린드롬을 만들기 위해 추가해야하는 문자 개수의 최솟값은 1 이다. d, c, [d] 이거나 [c], d, c 처럼 문자를 하나만 추가하면 팰린드롬이 완성되기 때문이다. 즉 (1, 2)의 값은 1이다. 

 

... 이렇게 쭉 채워나간 표가 아래의 표와 같다. 

index	j	0	1	2	3	4
i	str	a	d	c	b	a
0	a	0	1	2	3	2
1	d		0	1	2	3
2	c			0	1	2
3	b				0	1
4	a					0

여기서 우리가 원하는 답은 문자열 전체이다 즉 맨앞의 문자에서부터 맨뒤까지의 문자 모두 궁금한 것이다.

그래서 답은 (0, 4)의 값인 2이다.

 

여기서 우리는 규칙을 찾아내어 점화식으로 도출을 해내야한다.

생각을 해보면 

맨앞과 맨뒤의 문자가 같으면 우리는 별다른 고민없이 그다음앞과 그다음뒤의 문자를 비교해 나가면 될 것이다.

주어진 문자 맨앞 'a'와 맨뒤 'a'가 일치한다. 그러면 바로 우리는 다음 앞이 'd'와 다음 뒤 'b'를 비교하면 된다.

즉 'd'와 'b'의 최솟값이 곧 'a'와 'a'의 최솟값인거다. 이부분을 점화식으로 써보면

if str[i] == str[j]:
    dp_table[i][j] = dp_table[i-1][j-1]

이렇게 도출될 수 있다.

 

그 다음 'd'와 'b'를 보면 값이 다르다. 여기서 'd'의 인덱스는 i, 'b'의 인덱스는 'b'이다.

여기서 우리가 생각해볼 부분은 d 의 왼쪽에 [b]를 추가하는 경우이다.

[b] d ~ b 

이러면 b와 b가 대응이 됐으니

b [d ~   ] b

b와 b사이의 [d ~ ] 이부분을 팰린드롬으로 만들면된다.

즉 인덱스 번호를 보자면 i ~ j-1 인것이고 여기에 왼쪽에 b를 붙여줬기 때문데 +1을 해주면 최솟값이 나온다.

dp_table[i][j] = dp_table[i][j-1] + 1

다시 정리해보자면 [d ~ ]의 최솟값을 구하고 +1(왼쪽에 b)해주면 dp_table[i][j]의 최솟값이 된다.

 

근데 생각을 해보면 

d ~ b [d] 

마지막 요소의 오른쪽에 [d]를 붙이는 방법도 있다. 

이번에는 d [ ~ b] d 이렇게 나오고 

dp_table[i][j] = dp_table[i+1][j] + 1

위와 같이 공식화 시킬 수 있을 것이다.

 

최종 정리를 하면

dp_table[i][j-1] 경우와 dp_table[i+1][j] 경우의 최솟값 + 1을 해준 것이 결국

dp_table[i][j]이고 

dp_table[i][j] = min(dp_table[i][j-1], dp_table[i+1][j]) + 1

이런 점화식이 나오게 된다.

 

 

#코드

import sys
 
 
if __name__ == "__main__":
  
  getStr   = sys.stdin.readline()
  size     = len(getStr)
  dp_table = [[0]*(size) for _ in range(size)]
  
  for i in range(size-1, -1, -1):
    for j in range(i, size):
      if i == j:
        dp_table[i][j] = 0
      elif getStr[i] == getStr[j]:
        dp_table[i][j] = dp_table[i+1][j-1]
      else:
        dp_table[i][j] = min(dp_table[i][j-1], dp_table[i+1][j])+1
   
  print(dp_table[0][size-1])