[백준 2705번] 팰린드롬 파티션 (C++)

문제링크 : https://www.acmicpc.net/problem/2705

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

int dp[1001];

int cal(int n)
{
    if(n<1) return 0;
    else if(n<2) return 1; //n == 1
    
    if (dp[n] != -1) return dp[n]; //이미 있으면 반환
    dp[n] = 1;
    for (int i=0; i<=n/2; i++) dp[n] += cal(i); //절반에 가능한 값이 있으면 대칭으로 사용
    return dp[n];
}

int main() 
{
    int T, N;
    cin >> T;
    memset(dp, -1, sizeof(dp));
    while(T--)
    {
        cin >> N;
        cout << cal(N) << "\n";
    }

    return 0;
}

 

주어진 파티션에 대해 왼쪽 절반과 오른쪽 절반이 재귀적인 팰린드롬인지 체크해야한다.

따라서 입력받은 n을 기준으로 절반만 체크하며 절반에 가능한 값이 있으면 대칭으로 사용이 가능하기에 가능한 가짓수를 더한다.

 

재귀 과정에서 시간초과 방지를 위해 이미 값이 존재하면 바로 반환해주도록 한다.

그리고 기본적으로 dp[n]=1을 해주는데, 이는 현재 값 하나인 경우도 재귀이기 때문이다. (ex: 7)