풀이
d[i][j] = 문자열의 길이가 k이고, i행에서 시작해서 j행으로 끝나고, 그 문자열의 중심이 배열의 대각선(왼쪽 아래~오른쪽 위)에 있을 때, 그 문자열이 팰린드롬인 경우의 수
d[k][i][j] = d[k-2][i][j]+d[k-2][i+1][j]+d[k-2][i][j-1]+d[k-2][i+1][j-1]
식은 위와 같고, 배열은 k를 토글링 해서 n^2개만 사용할 것이다.
(1,1)~(n,n)의 문자열은 길이가 항상 홀수이다.
중앙의 diagonal 대각선을 기준으로, 팰린드롬의 길이를 앞뒤로 2씩 확장해 나갈 수 있다.
(a,b)~(c,d)의 중심이 대각선에 겹치려면, (a-1)+(b-1) = |(c-n)+(b-n)|을 만족해야 한다. (두 점이 각 끝점으로부터 떨어진 거리가 같아야 한다.)
a와 c를 O(n^2)에 각각 고정해서 i, j로 두자.
그러면 행 사이의 거리는 j-i이고, 열 사이의 거리는 k-(j-i)이면 된다. 이 식과 위의 식을 정리하면 아래와 같다.
b+d = 2n-j-i+2-b+d = k-j+i
두 식을 연립해서 풀면 b = n-i-(k/2), d = n-j+1+(k/2)이다.
이제 k, a, b를 고정했을 때, (a,b), (c,d)를 O(1)에 알 수 있게 되었다.
길이가 k이면서 (k+1)/2번째 문자가 대각선을 지나게 하는 좌표쌍을 알게 된 것이다.
그 좌표쌍의 두 문자가 같으면 위의 식을 계산해 주면 된다.
대충 오타가 있거나 식의 디테일이 틀렸을 수 있으므로 감안하자 ㅎㅎ
코드
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 1e9+7;
int n, d[555][555], t[555][555];
char a[555][555];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", a[i]+1);
d[i][i] = 1;
}
for (int k = 2; k <= n*2-2; k+=2) {
for (int i = 1; i <= n; i++) {
for (int j = n; j >= i; j--) {
if (n-i+1-(k/2) < 1 || n-j+1+(k/2) > n) continue;
if (a[i][n-i+1-(k/2)] != a[j][n-j+1+(k/2)]) continue;
t[i][j] = ((long long)d[i][j]+d[i+1][j]+d[i][j-1]+d[i+1][j-1])%mod;
}
}
memcpy(d, t, sizeof(d));
memset(t, 0, sizeof(d));
}
printf("%d\n", d[1][n]);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이