[Python/파이썬] 백준 1695번: 팰린드롬 만들기 / 파이썬 메모리초과 해결

문제

 

풀이

1. 주어진 수열에서 팰린드롬 수열을 구한다.

 

12342의 부분 수열 중 팰린드롬은 242(12342)이다.

 

2. 팰린드롬의 정 가운데를 기준으로 수열을 나눈다.

 

123    4    2

 

3. 팰린드롬이 아닌 수를 반대편에 추가한다.

 

123    4    321

 

수열에서 이미 팰린드롬인 수열을 구했고, 팰린드롬이 아닌 수만 추가하면 되므로 최적의 알고리즘이다.

 

 

또다른 예시

 

 

팰린드롬을 찾는 과정에서 DP가 이용된다.

 

[수열 A] 12342

[수열 A를 뒤집은 수열 B] 24321

이 있다고 가정해보자.

 

수열 A와 수열 B의 최장 공통 부분 수열(LCS)이 곧 팰린드롬 수열이다.

(수열 A를 뒤집었을 때의 부분 수열 = 수열 A의 부분 수열 이므로, 팰린드롬 수열의 조건을 생각해봐라)

 

 

말로 설명하기가 참 어렵다...

 

최장 공통 수열을 구하는 방법은 다음을 참고

https://ku-hug.tistory.com/120

[Python] 백준 9251번: LCS

 

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
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] == arr[j - 1]:
            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[-1][-1])

 

마무리

https://js1jj2sk3.tistory.com/45

백준) 1695 팰린드롬 만들기

 

원래 위 블로그를 참고하여 풀려했으나... 어떤 방법을 써도 메모리 초과가 나서 방법을 바꿨다...