1695. [Python]팰린드롬 만들기

1. 문제

 

https://www.acmicpc.net/problem/1695

 

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• DP(다이나믹 프로그래밍)

 

3. 파이썬 코드

 

N = int(input())
# 숫자 리스트 저장
num_list = list(map(int,input().split()))
# 리스트 역순으로 저장
reversed = num_list[::-1]
# LCS 적용 리스트
matrix = [[0] * (N+1) for _ in range(N+1)]
# 기존리스트와 역순 리스트 값을 비교해가며 같은 값의 경우 i-1, j-1 값을 +1 해줌 외의 경우 max 해서 위의 값과 왼쪽 값을 비교
for i in range(1,N+1):
    for j in range(1,N+1):
        if num_list[i-1] == reversed[j-1]:
            matrix[i][j] = matrix[i-1][j-1] + 1
        else:
            matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])

print(N-matrix[N][N])

 

4. 문제를 풀고난 후 생각

 

• 처음 문제에 접근한 방식은 queue 를 이용하여 오른쪽, 왼쪽에서 값을 뺴가며 왼쪽 left, right 투 포인터로 접근하는 방식으로 진행을 했고, 결과는 4%에서 바로 틀렸다. ( 반례는 찾지 못함 )
• 이후 접근하는 방식을 고민하다가 팰린드롬을 판단하는 기준이 결국 공통부분수열(LCS)와 비슷하다고 판단했고 DP로 접근했다.
• 실제로 고민을 해봤을때 숫자를 아무곳이나 끼워넣을 수 있기 때문에 공통부분수열 로직으로 구현해도 문제가 없었고 해결할 수 있었다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• DP(다이나믹 프로그래밍)
• LCS(Longest Common Subsequence)