728x90
programmers.co.kr/learn/courses/30/lessons/12904
코딩테스트 연습 - 가장 긴 팰린드롬
앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들
programmers.co.kr
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int solution(string s)
{
int answer=1;
int n = s.size();
vector<vector<bool>>check(n,vector<bool>(n,false));
for(int i=0; i<n; i++){
check[i][i]=true;
}
for(int i=0; i<n-1;i++){
if(s[i]==s[i+1]){
check[i][i+1]=true;
answer=2;
}
}
for(int k=3;k<=n; k++){
for(int i=0; i+k-1<n; i++){
int j = i+k-1;
if((check[i+1][j-1]==true) && (s[i]==s[j])){
check[i][j]=true;
answer = k;
}
}
}
return answer;
}- 대표적인 DP 문제이다.
- 백준에서 비슷한 문제를 풀어서 금방 풀 수 있었음.
