[Python/파이썬] 백준 1695번 팰린드롬 만들기

 

1695번: 팰린드롬 만들기

 

문제

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

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

입력

첫째 줄에 수열의 길이 N(1≤N≤5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다.

출력

첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다.

코드

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

# arr i번째까지의 수열과 arr의 역순수열의 j번째까지의 수열의 최장공통부분수열(LCS) 길이 저장
dp = [[0] * (n+1) for _ in range(n+1)]  

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

 

DP 배열에는 arr 수열의 i번째까지의 수열과 arr의 역순수열의 j번째까지의 수열의 최장공통부분수열(LCS)의 길이가 저장된다. DP배열의 값을 모두 계산해보면 결국 DP[n][n]에 arr 배열과 그 역순수열의 최장공통부분수열의 길이가 저장되게 되므로 이 값을 n에서 빼주면 정답을 구할 수 있다.

 

문제의 예제 1의 DP배열을 그려보면 위와 같다.

 

 

처음에 시도했던 코드 => 틀렸음

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

if n == 1:
    print(0)
    exit()
if n == 2:
    print(0 if arr[0] == arr[1] else 1)
    exit()
    
ans = 5000
# 하나씩 거꾸로 가며 확인
for i in range(n):
    prefix, suffix = i, i+2
    num = 0
    while suffix < n:
        if arr[suffix] == arr[prefix]:
            suffix += 1
            num += 1
        prefix -= 1
        if suffix == n:
            ans = min(ans, i+1-num)
        if prefix < 0:
            break
print(ans)

처음에는 수열을 2부분으로 나눠서 뒷부분 수열이 앞부분 수열의 부분수열이 되는지 여부를 판단하여 그것이 가능할 때의 앞부분 수열과 뒷부분 수열의 길이 차이를 구해주려고 하였다. 

처음부터 i번째까지의 수열의 역순수열(앞수열)과 앞수열이 끝나는 인덱스 2번째 이후의 수열(뒷수열)을 살펴보며 앞수열 prefix 인덱스의 값과 뒷수열 suffix 인덱스의 값이 같으면 suffix += 1, num += 1을 해주고 prefix의 값은 항상 +1을 해준다. 이렇게 진행하여 뒷부분 수열의 인덱스가 n까지 간다면 뒷수열이 앞수열의 부분 수열이 가능하다고 판단하여 이때의 앞부분 수열과 뒷부분 수열의 길이차이와 ans 값 중 작은 값을 ans에 저장한다.

 

처음에는 이렇게 풀이하였지만 틀렸다. 문제를 처음 읽었을 때 최장공통부분수열 알고리즘을 사용해야겠다는 생각은 들었는데 기억이 잘 안 나서 이렇게 풀었다가 방향이 아예 틀린것 같아서 구글링을 통해 도움을 얻고 위의 정답 코드와 같이 풀이하였다.