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

문제

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

아이디어

아래 블로그의 아이디어를 참고함
https://ddiyeon.tistory.com/67

최장 공통 부분수열(LCS: Longest Common Subsequence) 개념을 응용

코드

언어를 PyPy3로 설정해야 통과 (Python은 시간초과)

from sys import stdin


input = stdin.readline

length = int(input())
nums = list(map(int, input().split()))


lcs = [[0] * length for _ in range(length)]

for i in range(length):
    
    start = nums[i]

    for j in range(length):
        end = nums[length - 1 - j]

        if start == end:
            lcs[i][j] = 1

            if i > 0 and j > 0:
                lcs[i][j] += lcs[i-1][j-1]

        else:
            up = lcs[i-1][j] if i > 0 else 0
            left = lcs[i][j-1] if j > 0 else 0
            lcs[i][j] = max(up, left)


print(length - lcs[-1][-1])

개선점

나는 입력 길이에 딱맞게 배열을 만들어서 인덱스 체크가 필요했는데,
length+1 로 생성하고 0을 마진으로 뒀으면 체크할 필요가 없다..ㅠ