boj 14517

해결방법

다이나믹 프로그래밍이다.

점화식

dp[i][j] : [i,j]의 부분집합 중에서 팰린드롭의 갯수

dp[i][j] = dp[i+1][j] (i를 포함하지 않는 경우) 

+ dp[i][j-1] (j를 포함하지 않는 경우)

- dp[i+1][j-1] (i,j 둘 다 포함하지 않는 경우(교집합이 발생하므로 빼준다.))

+ str+i==str+j? dp[i+1][j-1]+1:0 (i,j가 같아서 i,j를 포함하는 경우 이때 +1하는 이유는 사이가 부분집합이 포함되어 있지 않으므로)

시간 복잡도 O(n^2)

초기 해결할때는 O(N^3)으로 풀었는데 풀이가 너무 복잡하여 시간복잡도를 줄인 방법으로 설명한다.

아래는 소스코드이다.

#include <iostream> 

#include <iterator>

#include <algorithm> 

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <string>

#include <cmath>

#include <cstdio>

#include <cstring>

using namespace std;

#define MOD 1000000007

#define INF 2147483647

#define LNF 9223372036854775807

#define pb push_back

#define mp make_pair

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll,ll> pll;

typedef pair<int,int> pii;

char str[1001];

int n,dp[1000][1000];

int main(){

freopen("sample.txt","r",stdin);

scanf("%s",str);

n = strlen(str)-1;

for(int i=0;i<=n;i++) dp[i][i]=1;

for(int j=1;j<=n;j++){

for(int i=0,k;j+i<=n;i++){

k=j+i;

dp[i][k]=(10007+dp[i][k-1]+dp[i+1][k]-dp[i+1][k-1]+(str[i]==str[k]?dp[i+1][k-1]+1:0))%10007;

}

}

printf("%d\n",dp[0][n]);

return 0;

}