DICT

AOJ DICT

idx	0	1	2	3	4	5	6	7	8
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1
7	1	7	21	35	35	21	7	1
8	1	8	28	56	70	56	28	8	1

SOL)

C[n+m][m] = C[n+m-1][m] + C[n+m-1][m-1];

맨 앞쪽의 문자를 생략했다고 생각
C[n+m-1][m-1]에서는 b를 추가
C[n+m-1][m]에서는 a를 추가 이런식으로 하면 테이블을 만들수있다.
k번째 문자열을 만들때에는 위 과정을 이용하여 역추적 방식을 사용한다.
n = 5, m =2, k =11일때
만약 C[6][2] > k 라면 11번째 문자열을 C[6][2]에서 포함되었다고 생각할 수있다.
즉, a가 문자열 맨 앞에 추가 됨을 알 수 있다.
다음은 C[5][2]를 보게 되는데 이때는 K가 더 크다. 그말은 b가 추가되어야 함을  알 수 있다.
하지만 여기서 k -= C[5][2]를 해주어야 하는데 그 이유는 C[5][1]이 의미하는것은
11번째 부터 15번째 문자열이 속해있임을 나타내는데 값은 5이므로 k -= C[5][2]을 해주어야한다.

[-] Collapse

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int C[201][201];
int main(){
    int t; cin >> t;
    while (t--){
        int n, m, k;
        cin >> n >> m >> k;
        C[0][0] = 1;
        for (int i = 1; i <= 200; i++) {
            C[i][0] = 1;
            C[i][i] = 1;
            for (int j = 1; j < i; j++)
                C[i][j] = min(C[i - 1][j] + C[i - 1][j - 1], 1000000001);
        }
        if (C[n + m][m] < k) {
            cout << "NONE" << endl;
            continue;
        }
        string s = "";
        int L = n + m;
        for (int i = 0; i<L; i++) {
            if (n>0 && C[n + m - 1][m] >= k) {
                s += "a";
                n--;
            }
            else {
                s += "b";
                k -= C[n + m - 1][m];
                m--;
            }
        }
        cout << s << endl;
    }
}