백준 #1256 사전


BOJ #1256 - 사전

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

# 문제 분류

DP

풀이 접근 방법


모르겠어서 justicehui님의 코드를 참고했다.

skip은 항상 어려운듯. 그리고 dp 배열을 dp[N+M][n]으로 가져가시는게 신기했다. 근데 skip 중에 쉬운거래서 놀람 ㅋㅋ


#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;
    }
}