백준 - 사전 (1256)

1. 문제 링크

문제 링크

2. 풀이

이항 계수를 이용해서 푸는 문제입니다.
a의 입장에서 생각해서 접근해 보겠습니다.

총 경우의 수

a는 n개, z는 m개가 있다면 (n + m)Cn이 됩니다.
즉 n + m개에서 n개를 뽑는 경우의 수입니다.
왜냐하면 n + m개에서 n개의 a를 배치하는 경우의 수와 동일하기 때문입니다.

K번째 문자열 만들기

문자열은 결국엔

• a_ _ _ _
• z_ _ _ _

이런 형태로 나아갈 겁니다.
즉, 현재 자리수에 a를 둘 건지, z를 둘 건지 결정하는 문제로 바꿀 수 있습니다.

• a를 둘 경우
  나머지 자리수에 a를 n - 1개를 두는 경우의 수가 k보다 크거나 같다는 뜻입니다.
  a를 출력하고, n을 1 감소시킵니다.
• z를 둘 경우
  나머지 자리수에 a를 n - 1개를 두는 경우의 수가 k보다 작다는 뜻입니다.
  z를 출력하고, k를 현 자리수에 a를 둔 경우의 수만큼 뺍니다.
  왜냐하면 z를 뒀다는 의미는 a를 뒀을 때 경우의 수를 다 스킵했다는 의미이기 때문입니다.

위 로직을 n + m번 반복하면 k번째 문자열을 얻을 수 있습니다.

3. 전체 코드

#include <bits/stdc++.h>

using namespace std;

int dp[201][201];

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

	int n, m, k;

	cin >> n >> m >> k;

	// 이항 계수 만들기 
	int at = min(n, m);
	dp[0][0] = 1;
	for (int i = 1; i <= n + m; i++) {
		dp[i][0] = dp[i][i] = 1;

		for (int j = 1; j <= at; j++)
			dp[i][j] = min(1000000000, dp[i - 1][j] + dp[i - 1][j - 1]); // k의 최댓값보다 커질 수 없도록(오버플로우 방지)
	}

	if (dp[n + m][n] < k) {
		cout << -1;
		return 0;
	}

	string ans = "";
	int len = n + m;

	// n + m 번 반복
	for (int i = len; i >= 1; i--) {
		// 나머지 자리수에 a를 n - 1개 배치한 경우의 수가 k보다 크거나 같을 때
		if (dp[i - 1][n - 1] >= k) {
			ans += 'a';
			n--;
		}
		else {
			ans += 'z';
			k -= dp[i - 1][n - 1]; // a를 앞에 두는 경우의 수를 넘어왔으므로 빼준다.
		}
	}

	cout << ans;

	return 0;
}