팰린드롬 만들기
면접 대비시간 제한2초메모리 제한128 MB
수열에 숫자를 삽입해 팰린드롬으로 만들 때 필요한 최소 삽입 개수를 구간 또는 LCS 기반 동적 계획법으로 구하는 문제입니다.
문제
앞에서부터 읽어도 뒤에서부터 읽어도 같은 수열을 팰린드롬이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}은 팰린드롬이지만, {1, 2, 3}과 {1, 2, 3, 2}는 팰린드롬이 아니다.
수열 하나가 주어진다. 이 수열의 원하는 위치에 수를 몇 개든 끼워 넣을 수 있을 때, 팰린드롬으로 만들기 위해 추가해야 하는 수의 최소 개수를 구하시오.
입력
첫째 줄에 수열의 길이 N이 주어진다. (1 <= N <= 5,000)
둘째 줄에 수열을 이루는 정수 N개가 주어진다. 각 정수는 int 범위에 들어간다.
출력
팰린드롬을 만들기 위해 끼워 넣어야 하는 수의 최소 개수를 출력한다.