[백준 1695번] 팰린드롬 만들기 (python)

문제

앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다.

한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.

 

기록

(dp 15일차) LCS 문제와 비슷해서 알고리즘 그대로 적용해서 풀었다. 수열과 역순으로 한 수열의 최장공통수열을 찾아내서 풀면 되는 문제. python3으로 하면 시간초과떠서 pypy3로 제출해야 할 것 같다. 

 

dp[i][j]에 역순으로 i번째까지 수와 순서대로 j번째까지 수의 최장공통수열 길이를 저장한다. 점화식은 두 가지 조건으로 나뉘는데, 현재 비교하는 숫자가 다르다면 dp[i-1][j] 혹은 dp[i][j-1] 중 큰 값을 저장하고, 비교하는 숫자가 같다면 dp[i-1][j-1]+1를 저장한다. dp 배열을 채우는 과정은 행 순서대로 아래와 같이 진행된다.

 

	1	2	3	4	2
2	0	1	1	1	1
4	0	1	1	2	2
3	0	1	2	2	2
2	0	1	2	2	3
1	1	1	2	2	3

 

코드

n = int(input())
seq = list(map(int, input().split()))

dp = [[0]*(n+1) for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        if seq[-i]==seq[j-1] : dp[i][j] = dp[i-1][j-1]+1
        else : dp[i][j] = max(dp[i][j-1], dp[i-1][j])
print(n-dp[n][n])

1. 수열의 역순으로 i번째까지와 순서대로 j번째까지의 최장공통수열 길이를 저장할 이차원 dp배열 생성

2. 각 숫자를 비교하며 숫자가 같으면 dp[i-1][j-1]+1을, 다르면 max(dp[i][j-1], dp[i-1][j])으로 계산하여 dp에 저장

3. 총 수열의 길이에서 수열과 역순 수열의 최장공통수열 길이를 빼서 출력한다.