2291번: Sequence

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

$O(nm)$

dp[n][m]를 항이 n개이고 합이 m인 본 수열의 개수라고 정의하면

dp[0][0]=1

dp[i][j]=dp[i][j-i]+dp[i-1][j-1]

수열은 대응관계를 이용해서 앞자리부터 복원합니다.

f(n,m,k): 항이 n개이고 합이 m인 k번째 수열

이 함수가 호출되었다고 합시다.

a[1]=1을 가정했을 때의 수열 개수가 k보다 크거나 같은 경우(k<=dp[n-1][m-1]) a[1]=1이라는 것을 알 수 있습니다.

수열의 다음 항들은 다음과 같이 적절히 대응시킬 수 있습니다.

f(n,m,k) = {a[1]=1, a[2...n]=f(n-1,m-1,k)}

a[1]=x를 가정했을 때의 수열 개수가 k보다 작은 경우(k>dp[n-1][m-1]) a[1]이 더 커져야 함을 알 수 있습니다.

a[1]=x+1인 수열과 a[1]=x인 수열은 다음과 같이 적절히 대응시킬 수 있습니다.

곧 f(n, m, k) = f(n, m-n, k-dp[n-1][m-1])인 수열의 각 자리에 1씩 더한 수열

이러한 재귀적인 성질은 아래와 같은 간단한 반목문(8~11번째 줄)을 통해 구현할 수 있습니다.

#include<cstdio>
int dp[11][221] = { 1 }, n, m, k;
int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= m; j++)
            dp[i][j] = dp[i][j - i] + dp[i - 1][j - 1];
    for (int i = 1; n--, m--;) {
        for (; k > dp[n][m]; i++) k -= dp[n][m], m -= n + 1;
        printf("%d ", i);
    }
    return 0;
}