문제 설명
재귀적인 팰린드롬 수열의 합이 N인 수열의 개수를 찾는 문제입니다.
풀이
재귀적인 팰린드롬이란 수열이 주어져 있을 때 팰린드롬이어야 하고 수열의 왼쪽 절반과 오른쪽 절반도 재귀적인 팰린드롬이어야 합니다.
예를 들어
1312131
이렇게 전체가 우선 팰린드롬이고 왼쪽 절반 131, 오른쪽 절반 131이 재귀적인 팰린드롬이므로 1312131 은 재귀적인 팰린드롬입니다.
1223221
이 수열은 팰린드롬이지만 왼쪽 절반 122, 오른쪽 절반 221 이 재귀적인 팰린드롬이 아니므로 1223221은 재귀적인 팰린드롬이 아닙니다.
이 문제를 완전 탐색으로 합이 n인 모든 수열을 구해서 재귀적인 팰린드롬인지 판별하면 시간 초과가 날 수밖에 없습니다.
그래서 저는 모든 수열을 구하여 재귀적인 팰린드롬인지 판별하기보단 팰린드롬인 수열을 만들어 가는 방법으로 생각해보겠습니다.
음? 어떻게?
재귀적인 팰린드롬 수열 x 가 있다고 하겠습니다.
x, xx, x1x, x2x, x3x, ··· 모두 재귀적인 팰린드롬입니다.
이를 이용하여 점화식을 구할 수 있습니다.
DP[n] = 합이 n인 재귀적인 팰린드롬 수열의 개수
DP[n] = DP[n] + DP[(n - i) / 2] (0 <= i <=n)
기본적으로 DP[i]은 1이라는 값을 갖고 있습니다.
i 자체가 재귀적인 팰린드롬이기 때문이죠. ex) 1,2,3, ···
그리고 n에서 가운데 숫자 i를 뺐을 때 남은 수열의 합은 n-i이고 n-i을 2로 나누어 양쪽에 재귀적인 팰린드롬 수열의 개수 DP[(n-i)/2]를 더하게 되면 중앙에 숫자 i가 있을 때 합이 n인 재귀적인 팰린드롬 개수를 구할 수 있습니다.
단, n - i이 홀수 일 때는 정확히 반으로 나눌 수 없기 때문에 더하지 않습니다.
이렇게 하면 쉽게 답을 구할 수 있습니다..!
꺄ㅑㅑㅏㅏㅏ
처음에 재귀적인 팰린드롬이란 말이 이해가 안 돼서
어렵게 생각하고 있었는데 그냥 DP 문제였네요!
정답률이 79.8%라 놀라고 정답률 떨어지지 않게 데이터 다 구해보고 조심스레 제출했습니다…
다행히 1트 성공했네요 ㅎㅎ
정답률이 떨어지지 않아 다행입니다 ㅎㅎㅎ
소스 코드
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int main(){
FIO;
int dp[1005];
FOR(i,1,1000) dp[i] = 1;
FOR(i,1,1000) FOR(j,0,i - 1){
if((i - j) & 1) continue;
dp[i] += dp[i - j >> 1]; // (i - j >> 1) == ((i - j) / 2)
}
int t; cin >> t; while(t--){
int n; cin >> n;
cout << dp[n] << '\n';
}
return 0;
}