[BOJ] (G3) 1695. 팰린드롬 만들기

👨‍💻 개인 공부 기록용 블로그 입니다.
💡 틀린 내용이나 오타는 댓글, 메일로 제보해주시면 감사하겠습니다!! (__)

링크

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

문제

문제 설명 및 요점

• 수열이 주어졌을 떄, 팰린드롬을 만들기 위해 수를 끼워 넣으려고 한다.
• 최소 개수를 끼울 때, 해당 개수를 구한다.

풀이

#DP #문자열

• 팰린드롬 여부는 재귀적으로 검사할 수 있다. 맨 앞과 맨 뒤 글자가 같다면, 그 다음 위치로 옮겨 검사하면 된다. 예를 들어 ‘1231’ 문자열이 있다면, 시작과 끝이 1로 같으니 그 다음엔 앞뒤로 한 칸씩 움직여 2와 3을 검사하는 식이다.
• 위 원리를 이용하여 부분 문자열을 팰린드롬으로 만들기 위해 끼워 넣어야 하는 문자 개수를 계산할 것이다. 부분을 계산하여 합치면, 전체 개수를 구할 수 있다.
• dp[i][j] = i번째 문자부터 j번째 문자까지를 부분 문자열로 볼 때, 팰린드롬으로 만들기 위해서 끼워 넣어야 하는 최수 문자 개수
• 2차원 테이블을 0으로 초기화 시킨 뒤, 부분 문자열의 길이를 1부터 보면서 테이블을 채워 나간다.
  • 1글자는 무조건 팰린드롬이다.
  • 2글자는 앞뒤 문자가 같은 지 검사하면 된다.
  • 3글자부터는 앞뒤 문자가 같은지, 다른지에 따라 선택지가 갈린다.
  • 앞뒤가 같다면, 내부만 팰린드롬으로 만들면 되므로 이전 값(처음+1, 끝-1)을 그대로 가져온다.
  • 앞뒤가 다르다면, 앞 글자를 맨 뒤에 끼울 것인지 또는 뒷 글자를 맨 앞에 끼울 것인지 비교한다.
• 위와 같은 방식으로 테이블을 채우면, 맨 처음 - 맨 뒤 부분 문자열(입력 문자열과 같은 형태)에 해당하는 인덱스를 참조하여 정답을 얻을 수 있다.

코드

import sys
input = sys.stdin.readline

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

dp = [[0] * n for _ in range(n)]

for d in range(1, n):
    for i in range(n - d):
        if nums[i] == nums[i + d]:
            dp[i][i + d] = dp[i + 1][i + d - 1]
        else:
            dp[i][i + d] = min(dp[i + 1][i + d], dp[i][i + d - 1]) + 1

print(dp[0][n - 1])