BOJ #1256 - 사전

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define fup(i, a, b, dp) for (int(i) = (a); (i) <= (b); (i) += (dp))
#define fdn(i, a, b, dp) for (int(i) = (a); (i) >= (b); (i) -= (dp))
#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int N, M, K;
ll dp[210][210];

string ans;

void skip(int n, int m, int k) {
    if (n == 0) {
        fup(i, 0, m - 1, 1) {
            ans += 'z';
        }
        return;
    }
    if (m == 0) {
        fup(i, 0, n - 1, 1) {
            ans += 'a';
        }
        return;
    }

    ll cnt = dp[n - 1 + m][m];
    if (k <= cnt) {
        ans += 'a';
        skip(n - 1, m, k);
    } else {
        ans += 'z';
        skip(n, m - 1, k - cnt);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    dp[1][0] = dp[1][1] = 1;
    fup(i, 2, 200, 1) {
        fup(j, 0, i, 1) {
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            if (dp[i][j] >= INF)
                dp[i][j] = INF + 1;
        }
    }

    cin >> N >> M >> K;

    if (K > dp[N + M][M])
        cout << "-1";

    else {
        skip(N, M, K);
        cout << ans;
    }
}