[백준] 1256 - 사전

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

1256번: 사전

 

dp + 조합론 문제였다.

 

문제를 간단히 정리하자면,

n개의 a와 m개의 z로 구성된 모든 문자열 중 k번째 문자열을 구하는 문제이다.

 

n과 m의 제한이 100이므로, 모든 모든 조합을 구하는 것은 TLE가 날 것이고 따라서 dp를 이용할 것이다.

k번째 문자열을 구하는 것은 어떻게 할 수 있을까?

 

처음 상황을 보자.

만약 첫번째 자리에 a를 배치했다고 하면,

남은 총 문자열의 길이는 (n + m - 1)이고, 이 중에 (n - 1)개의 a를 배치하면, 자동으로 m개의 z는 배치가 완료된다.

따라서 (n + m - 1)C(n - 1) 이다.

만약 이 값이 구하려는 k보다 크다면, 해당 위치에 z를 배치하고 작거나 같다면 a를 배치하면 된다.

 

#include <iostream>
#include <cstring>
using namespace std;

long long dp[201][101];

long long comb(int n, int r) {
	if (n == r || r == 0)return 1;
	if (dp[n][r] != -1)return dp[n][r];
	long long ret1 = 0, ret2 = 0;
	ret1 = comb(n - 1, r - 1);
	ret2 = comb(n - 1, r);
	if (ret1 + ret2 > 1000000000)return dp[n][r] = 1000000001;
	else return dp[n][r] = ret1 + ret2;
}

void go(int n, int m, long long k) {
	long long c = comb(n + m - 1, n - 1);
	if (n > 0 && k <= c) {
		cout << 'a';
		go(n - 1, m, k);
	}
	else if (m > 0) {
		cout << 'z';
		go(n, m - 1, k - c);
	}
}

int main() {
	int n, m;
	long long k;
	cin >> n >> m >> k;
	memset(dp, -1, sizeof(dp));
	if (comb(n + m, n) < k)cout << -1;
	else go(n, m, k);
}