프로그래머스 Level 3 가장긴팰린드롬

가장긴팰린드롬 (프로그래머스 Level 3)

https://school.programmers.co.kr/learn/courses/30/lessons/12904

역시 처음에는 브루트 포스로 풀어보았는데
O(n^3)이 되기에 시간초과가 발생하였고
반례를 찾던 중
dp로 풀 수 있다는 힌트를 주워들어 곰곰히 생각해본 결과

1. 팰린드롬의 시작과 끝은 같은 문자여야 한다
   
2. 팰린드롬의 시작과 끝을 제거한 문자열 역시
   팰린드롬이여야 한다 (부분 문자열)
   => DP를 통해 풀 수 있음
   

다만 고민이였던 점은
팰린드롬의 길이가 ‘홀수’냐 ‘짝수’냐에 따라 결과가 나뉠 것 같다 생각하였지만
처음 자기자신의 dp[i][i] 를 지정하고,
‘양 옆에 같은 문자열이 있는 경우’를 추가적으로 포함시킴으로서
‘짝수’ 길이에 대한 dp 처리가 가능하다는 것을 확인할 수 있었다
ex: ‘abaaba’ -> 중간의 ‘aa’ 부분을 팰린드롬인 것을 확인 가능

dp[i][j] : i~j까지 인덱스가 ‘팰린드롬’이면 true

따라서 ‘점차적’으로 길이를 늘여나가며
특정한 인덱스 i와 길이 length 에 대하여
s[i] == s[i + length - 1(인덱스 처리용)] 이라면
dp[i-1][i + length - 2] 가 true인지 확인하는 것으로 중복 계산을 피할 수 있었다

dp는 항상 개념을 ‘적용’하는 것이 제일 어렵다는 것을 느끼는 중이다

Code

#include <string>
#include<vector>

using namespace std;

int solution(string s){
    int answer = 1;
    const int sSize = s.size();

    vector<vector<bool>> dp(sSize, vector<bool>(sSize, false));

    for (int i = 0; i < sSize; i++)
    {
        dp[i][i] = true;
    }

    for (int i = 0; i < sSize - 1; i++)
    {
        if (s[i] == s[i + 1])
        {
            answer = 2;
            dp[i][i + 1] = true;
        }
    }

    // 크기가 3이상인 경우
    for (int length = 3; length <= sSize; length++)
    {
        for (int i = 0; i <= sSize - length; i++)
        {
            if (s[i] == s[i + length - 1])
            {
                if (dp[i + 1][i + length - 2])
                {
                    answer = length;
                    dp[i][i + length - 1] = true;
                }
            }
        }
    }

    return answer;
}