백준 1256번 [사전]

dp로 조합 다루기

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

	ll n, m, k;
	string ans = "";
	cin >> n >> m >> k;

	ll dp[201][201];
	for (int i = 0; i <= 200; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0 || i == j) dp[i][j] = 1;
			else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
			if (dp[i][j] > 1000000000) dp[i][j] = 1000000001;
		}
	}

	if (dp[n + m][n] < k) cout << -1;
	else {
		ll cnt = m;
		for (ll i = n+m-1; i >= 0; i--) {
			if (cnt == 0) {
				ans += "a";
			}
			else if (i+1 == cnt) {
				ans += "z";
				cnt--;
			}
			else if (dp[i][cnt] >= k) {
				ans += "a";
			}
			else {
				ans += "z";
				k -= dp[i][cnt];
				cnt--;
			}
		}
		cout << ans;
	}

	return 0;
}