코드 복사/붙여넣기 하는 당신이 아름답습니다.

10759: 팰린드롬 경로3

풀이

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)|을 만족해야 한다. (두 점이 각 끝점으로부터 떨어진 거리가 같아야 한다.)

acO(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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2019-09-15 19:21

Read more posts by this author