해결과정 - DP첫번째 방법 무식하게 푸는 방법은 모두가 생각한듯이 S, E가 주어졌을때 {S, E} {S - 1, E - 1} 이런식으로 비교를 해가며 푸는 방식이다 하지만 질문 M이 많을경우 약 n^2 * m의 시간복잡도가 발생하게 된다 두번째 방식은 S와 E의 값이 같을때 S와 E의 안쪽이 팰린드롬이면 S 와 E도 팰린드롬이라는 것에서 미리 팰린드롬 보드를 제작할수 있다 1일때는 팰린드롬임이 분명하고 2일때부터 위의 발상을 적용할 수 있다 위를 표현하면if(S == E) 일때 board[Length][Start] = board[Length - 2][Start + 1] 이라는 공식이 나오게 된다계산의 편리성을 위해 board는 1부터 시작하도록 구성하였다 #include#include#include#..
