[1256] 사전

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

1256번: 사전

꽤 자주 보이는 조합론&dp 문제

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

ll n, m, k, dp[201][201];

ll c(ll A, ll B) { return dp[A + B][B]; }

void f(ll i, ll j, ll idx) {

    if (i == 0 && j == 0) return;

    if (i == 0) {

        cout << 'z';

        f(i, j - 1, idx);

        return;

    }

    if (j == 0) {

        cout << 'a';

        f(i - 1, j, idx);

        return;

    }

    ll nxt = c(i - 1, j);

    if (nxt >= idx) {

        cout << 'a';

        f(i - 1, j, idx);

    } else {

        cout << 'z';

        f(i, j - 1, idx - nxt);

    }

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m >> k;

    ll i, j;

    for (i = 0; i <= 200; i++) dp[i][0] = dp[0][i] = 1;

    dp[1][1] = 1;

    for (i = 2; i <= 200; i++)

        for (j = 1; j <= 200; j++)

            dp[i][j] = min(dp[i - 1][j] + dp[i - 1][j - 1], (ll)1e9);

    if (k > c(n, m)) {

        cout << -1;

        return 0;

    }

    f(n, m, k);

    return 0;

}

---