SWEA 4699 - 콩순이의 가장 싼 팰린드롬 D-Ⅳ 이 문제는 SWEA 문제입니다. 문제 출처 : 콩순이의 가장 싼 팰린드롬 Palindrome 이란? 팰린드롬이란 문자열, DP 문제에서 종종 접할 수 있는 문제이다. 팰린드롬을 가장 쉽게 표현하자면 거꾸로 해도 똑같은 문자라고 할 수 있다. 예를 들어, ABBA 와 같이 거꾸로 해도 똑같은 문자를 의미한다. How to Solve? 처음에는 문자를 제거하고 삽입하는 모든 경우를 탐색하면서 팰린드롬이 완성됐다면 Cost 값을 저장해두고 해당 Cost보다 큰 경우는 바로 탐색 종료하는 방식의 BackTracking 방식으로 구현했다. 하지만 이 문제의 Stack 메모리 제한이 있기에 재귀로 해결하기 어렵다. 따라서 다른 방식의 접근이 필요하다. 앞서 Palindrome을 설명하면서 DP에서 자주 나온다고 설명했다. 따라서 이 문제에서도 DP를 활용한 접근 방법을 알아본다. 🔥 DP 핵심은 가장 인접한 두 글자부터 팰린…