BOJ(백준) 14505, 14517번 팰린드롬 개수 구하기

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

14517번: 팰린드롬 개수 구하기 (Large)

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

14517번: 팰린드롬 개수 구하기 (Large)

문자열의 크기만 다르고 같은 방식으로 풀리는 두 문제이다. 풀이는 다음과 같다.

 

문자열의 길이가 N이라고 할 때 N*N 사이즈의 2차원 dp배열을 만든다.

dp[i][j]는 문자열의 인덱스 i번부터 j번까지로 만들 수 있는 팰린드롬 부분 문자열의 개수이다.

 

구간의 길이가 1~N일 때의 부분 문자열의 개수를 차례대로 구할 것이다.

 

우선은 길이가 1일 때는 항상 개수가 1이므로 (0<=i<N) dp[i][i]=1로 초기화한다.

다음으로 길이가 2일 때는  (0<=i<N-1) dp[i][i+1]을 두 문자가 같으면 3, 아니면 2로 초기화 한다.

길이가 3일 때부터는 두가지 상황에 따라 다음과 같은 서로 다른 점화식을 적용할 수 있다. 

 

i번 문자와 j번 문자가 다른 경우: dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];

i번 문자와 j번 문자가 같은 경우: dp[i][j]=dp[i+1][j]+dp[i][j-1]+1;

 

i번 문자와 j번 문자가 다른 경우에는  dp[i+1][j]+dp[i][j-1]에서 dp[i+1][j-1]부분이 겹치므로 빼주는 것이다.

i번 문자와 j번 문자가 같은 경우에는  dp[i+1][j]+dp[i][j-1]에서 dp[i+1][j-1]부분이 겹치는 것은 같으나 dp[i+1][j-1]에서 만든 팰린드롬 부분 문자열에 i번 문자와 j번 문자를 더해 똑같은 개수만큼의 팰린드롬 부분 문자열을 추가로 만들어 줄 수 있으니 뺄 필요가 없고, 추가로 i번 문자와 j번 문자만으로 하나의 팰린드롬을 더 만들 수 있으니 1을 더해주는 것이다.

 

Large문제에서 small과 다르게 주의할 점은 i번 문자와 j문자가 다를 때 마이너스를 하다보니 가끔 음수가 되어 모듈러 연산이 이상하게 될 수 있다는 점이다. 따라서 연산 전 MOD값 만큼 더해주는 모듈러 연산을 해주면 AC를 받는 것이 가능하다.

 

AC code

#include <bits/stdc++.h>
using namespace std;
string s;
long long dp[1000][1000],len,MOD=10007;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>s;
	len=s.length();
	for(int i=0;i<len;i++) dp[i][i]=1;
	for(int i=0;i<len-1;i++) dp[i][i+1]=s[i]==s[i+1]?3:2;
	for(int i=2;i<len;i++) for(int k=0;k<len-i;k++) dp[k][k+i]=(MOD+dp[k+1][k+i]+dp[k][k+i-1]+(s[k]==s[k+i]?1:-dp[k+1][k+i-1]))%MOD;
	cout<<dp[0][len-1]; 
}

 

dp는 공부를 아무리 많이 해도 처음 보는 참신한 유형의 문제가 끝도 없이 많은 것 같다.