문제 바로가기
문제:
앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.
입력:
첫째 줄에 수열의 길이 N(1≤N≤5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다.
출력:
첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다.
풀이:
import sys
sys.setrecursionlimit(100000)
def solution(sequence):
n = len(sequence)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if sequence[i] == sequence[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
N = int(input())
sequence = list(map(int, input().split()))
print(N - solution(sequence))
이 문제는 LCS 를 사용해서 푸는 문제같다
LCS는 두 문자열에서 가장 긴 공통 부분 수열을 찾는 알고리즘이다.
(Python/🥇4)백준알고리즘 9251번: LCS
문제바로가기 문제: LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 A
windy7271.tistory.com
여기에서 한 번 했다.
이를 응용하여 주어진 수열과 그 수열의 뒤집은 수열 사이에서 가장 긴 공통 부분 수열을 찾으면, 그것이 팰린드롬 부분 수열이 됩니다.
예를 들어, 주어진 수열 sequence = [1, 2, 3, 4, 2]에서 LCS를 구하는 방법은 주어진 수열을 그대로 두고, 그대로 뒤집은 새로운 수열 reversed_sequence = [2, 4, 3, 2, 1]을 만든다.
LCS 알고리즘을 사용하여 sequence와 solution 사이에서 가장 긴 공통 부분 수열을 구합니다.
이 공통 부분 수열이 팰린드롬 부분 수열이 됩니다.
그리고 최종적으로 나온 팰린드롬 부분수열을 N에서 빼주면 나머지 공간에 숫자를 채워주면 된다.
예를들어 12342 면 242가 공통수열이다 .그럼 1과 3이 하나씩 부족하므로 1과 3 1개씩 추가 해주면 된다.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
sys.setrecursionlimit(100000)
import sys
import sys
def solution(sequence):
n = len(sequence)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if sequence[i] == sequence[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
N = int(input())
sequence = list(map(int, input().split()))
print(N - solution(sequence))
dp는 2차원 배열이고 dp[i][j] 가 가르키는 뜻은 dp[i에서][j까지] 의 LCS를 찾는 것이다.
for i in range(n):
dp[i][i] = 1그러면 자기자신은 팰린드롬이니깐 1로 초기화해준다.
포문을 돌리면서
길이가 2개 3개 4개 이렇게 포문을 돌리면서 찾는거다
i는 시작점이고 j는 마지막지점이다. 그럼 길이가 2일때 시작점과 마지막점이 같으면 팰린드롬 수열인 것이다. 시작점 +1 마지막점 +1 에 +2 를 해주면 팰린드롬 길이가 나온다.
예를들면 1 2 1 이면
2는 이미 자기 자신이므로 1 이고
1 1 이 같으므로 3이 된다는 것이다.
이제 다를 경우인데 다를경우에는
1 2 3 4 2 라고 했을때
- 1 2 3 4 2 1 >> 뒤에 1을 추가
- 2 1 2 3 4 2 >> 앞에 1을 추가
이렇게 2 가지 경우가 남는데 둘중에 더 큰 값이 들어가게 된다.
댓글