이모저모
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;
}