[프로그래머스/Level 3] 가장 긴 팰린드롬 (C++)

programmers.co.kr/learn/courses/30/lessons/12904

코딩테스트 연습 - 가장 긴 팰린드롬

DP를 이용하여 팰린드롬의 길이가 가장 긴 경우를 찾는 문제입니다. 예전에 풀었던 백준 10942번을 참고했습니다.

 

#include <string>
using namespace std;

bool dp[2501][2501];

int solution(string s)
{
    int answer = 1;
    
    for(int i = 0; i < s.size(); i++) {
        dp[i][i] = true;
    }
    
    for(int i = 0; i < s.size() - 1; i++) {
        if(s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            answer = 2;
        }
    }
    
    for(int len = 3; len <= s.size(); len++) {
        for(int i = 0; i < s.size() - len + 1; i++) {
            int j = i + len - 1;
            if(s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                answer = len;
            }
        }
    }

    return answer;
}