6362 - Unimodal Palindromic Decompositions

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

$N=7$일 때 아래와 같이 표현할 수 있다.

[그림 1]

가운데 숫자를 회색숫자(1,2,3..)만큼 쪼개서 양쪽에 붙인다고 생각했다. [그림 1]은 해석하면 [그림 2]와 같은 뜻이다.

[그림 2]

하지만 문제의 정의상 가운데에서 끝으로 갈수록 숫자가 (같거나) 작아야하므로 (3 1 3) 이나 (1 2 1 2 1) 같은 수열은 정답으로 셀 수 없다. 따라서 쪼개는 수(회색숫자)를 $k$라고 했을 때, $k \le n-2k$ 인 경우에만 쪼갤 수 있다. 

$k$는 쪼개서 옆에 붙인 숫자이다. 이 말은 가장 끝에 $k$ 보다 큰 수는 없다는 것이다. 항상 $k=1$ 가 아닌 $k=$이전의 $k_{prev}$ 부터 시작해야 한다.

짝수의 경우 역시 위와 동일하게 진행하되, (8) -> (4 4) 와 같은 경우가 가능하기 때문에 $k \le \frac{n}{2}$ 인지를 더해준다.

참고로 $N=8$ 일 때 (1 2 2 2 1) 에서 (1 2 1 1 2 1) 을 안 세도록 해야한다.

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

#define INF 987654321

typedef long long lld;

lld dp[300][300];

lld f(int n, int k){
    if(n < 0) return 0;
    if(n <= 1) return 1;
  
    lld& r = dp[n][k];
    if(r != -1) return r;
  
    r = 1;
    for(int i=k; i <= n-2*i; ++i){
        r += f(n-2*i, i);
    }
    if(n%2 == 0){
        r += k <= n/2;
    }
    return r;
}

int main(){
    int n;
    memset(dp, -1, sizeof(dp));
    while(~scanf("%d", &n) && n){
        printf("%d %lld\n", n, f(n, 1));
    }
    return 0;
}