백준 14517 - 팰린드롬 개수 구하기 (Large)

https://www.acmicpc.net/problem/14517

풀이

다음 테이블을 세운다.

 

dp(i, j) := i번째 문자부터 j번째 문자까지 해서 부분 수열을 구성했을 때 나올 수 있는 팰린드롬의 갯수

 

그러면 dp(i, i) = 1, dp(i, i + 1) = 2로 초기화를 할 수 있다. 이 때 입력으로 주어진 문자열 s에 대해 s[i] = s[i + 1]이면 대칭인 팰린드롬이 존재하는 것이므로 dp(i, i + 1) = 3이 된다.

 

그리고 부분 수열이 가질 수 있는 범위 gap마다 반복문을 돌면서 다음을 더하거나 빼면 된다.

 

시작점이 i이고 끝점이 j일 때...

 

dp(i + 1, j)에서 그대로 가져오는 경우 -> dp(i, j)에서 단순히 확장한 것으로 간주할 수 있다.

 

dp(i, j - 1)에서 그대로 가져오는 경우 -> dp(i, j)에서 단순히 확장한 것으로 간주할 수 있다.

 

두 경우를 더하면 dp(i + 1, j - 1)에서 중복으로 더한 부분이 발생하리란 것은 당연하다. 따라서 dp(i + 1, j - 1)을 빼서 중복을 제거해야 한다.

 

그리고 s[i] = s[j]이면 두 문자가 대칭이라는 소리다. 따라서 다음 그림을 따라 dp(i + 1, j - 1)에 해당하는 부분을 다시 더할 필요가 있다.

 

 

위 계산을 통해 dp(0, n - 1)까지 구하면 정답이 된다. 모듈러 연산에 각별히 유의하도록 하자.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
const int mod = 10007;
string s;
int dp[1000][1000];
int n;
 
void solve()
{
  cin >> s;
  n = s.size();
  for (int i = 0; i < n; i++) dp[i][i] = 1;
 
  for (int i = 0; i < n - 1; i++)
  {
    dp[i][i + 1] = 2;
    if (s[i] == s[i + 1]) ++dp[i][i + 1];
  }
 
  for (int gap = 2; gap < n; gap++)
  {
    for (int i = 0; i + gap < n; i++)
    {
      int j = i + gap;
      int &cur = dp[i][j];
      cur += dp[i + 1][j];
      cur += dp[i][j - 1];
      cur -= dp[i + 1][j - 1];
      while (cur < 0) cur += mod;
      cur %= mod;
 
      if (s[i] == s[j]) cur += dp[i + 1][j - 1] + 1;
      cur %= mod;
    }
  }
  cout << dp[0][n - 1];
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록