[백준] 2291 - Sequence

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

2291번: Sequence

 

길이가 최대 10, 합이 최대 220인 수열을 만들었을 때, k번째 비내림 차순 수열을 구하는 문제이다.

모든 경우의 수를 탐색하는 방법으로는 당연히 시간초과가 날 것이므로 다른 방법을 찾아야 한다.

 

N = 4, M = 9 일 때

첫 번째 수가 1일 경우 뒤에 수열을 몇 가지 만들 수 있을까?

1 1 X X

1 2 X X

1 3 X X

..

이 경우에서 1 3 X X는 가능하지 않다. 왜냐하면 X X의 최솟값은 3 3 = 6인데, 1 3 3 3의 수열의 합은 10이기 때문이다.

그렇다면 1 1 X X의 경우는 몇 가지가 있을까?

1 1 1 X

1 1 2 X

1 1 3 X

이렇게 3가지가 있다.

 

여기서 알아볼 수 있는 점은, "수열의 길이"와 "수열의 합"과 "수열의 마지막 수"에 따라서 경우의 수를 구할 수 있다는 것을 알 수 있다.

따라서 다이내믹 프로그래밍을 적용시킬 것이고,

dp[i][j][k] = 길이가 i이고, 합이 j이며, 마지막 문자가 k일 경우 수열의 경우의 수

라고 정의하자.

그렇다면 다음과 같은 점화식을 세울 수 있다.

for (int it = k; it <= m; it++) {
	dp[i][j][k] += dp[i + 1][j + it][it];
}

경우의 수는 구했으면, K번째 경우의 수를 구하는 방법은 간단하다.

수열의 처음부터 끝까지 문자 하나하나를 비교하며 남은 경우의 수를 빼주면 된다.

#include <iostream>
#include <cstring>
using namespace std;

int dp[11][221][221], n, m, k;

int go(int len, int sum, int recent) {
    if (len > n || sum > m) {
        return 0;
    }
    if (dp[len][sum][recent] != -1) {
        return dp[len][sum][recent];
    }
    int res = 0;
    for (int i = recent; i <= m; i++) {
        res += go(len + 1, sum + i, i);
    }
    return dp[len][sum][recent] = res;
}

void go2(int len, int sum, int recent, int left) {
    if (len == n) {
        return;
    }
    
    for (int i = recent; i <= m; i++) {
        if (dp[len + 1][sum + i][i] == -1) {
            continue;
        }
        
        if (left > dp[len + 1][sum + i][i]) {
            left -= dp[len + 1][sum + i][i];
            continue;
        }
        
        cout << i << ' ';
        go2(len + 1, sum + i, i, left);
        break;
    }
}

int main() {
    cin >> n >> m >> k;
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= m; i++) {
        dp[n][m][i] = 1;
    }
    go(0, 0, 1);
    go2(0, 0, 1, k);
}