백준 1256 사전 - C++

최대 100개의 a와 100개의 z로 이루어진 문자열이 있다.

이를 사전 순으로 정리했을 때 k 번째 문자열이 무엇인지 알아내면 된다.

K는 여기서 1억까지 가능하며, 문자열의 개수가 K보다 작으면 -1이다.

 

a 가 3개, z 가 2개 있는 상황을 생각해 보자.

1. aaazz 

2. aazza

3. aazaz

4. azaaz

5. azaza

6. azzaa

7. zaaaz

8. zaaza

9. zazaa

10. zzaaa

까지 총 10가지이며, 이는 고등학교? 중학교? 에서 배우는

순열과 조합에서 알 수 있다. (N+M)!/ N!/M!

 

여기서 트릭을 좀 쓸 수 있다.

위의 식에서 즉 조합은 nCk = n-1Ck + n-1Ck-1로 하나씩 줄일 수 있고,

n-1Ck = n-2Ck + n-2Ck-1로 다시 나눌 수 있다.

이렇게 갈 경우 기저케이스는 nCn = 1과 nC1 = n 혹은 nC0 = 1인 경우이다.

 

다시 보면 위에서 본 식은 조합으로 표현 가능하다.

(n+m)! / (n! m!) =  (n+m) C (n)

 

위 식은 다시 표현하면

(n+m) C (n)  = (n+m-1) C (n-1) + (n+m-1) C (n) 

 

식 하나하나를 잘 보면

(n+m-1) C (n-1) 은 a를 하나 줄였을 때 만들 수 있는 경우의 수와 같고

(n+m-1) C (n) = (n+m-1) C (m-1) 이므로 z를 하나 줄였을 때 만들 수 있는 경우의 수다.

 

즉, 총 만들 수 있는 경우의 수 = a 를 하나 줄였을 때 만들 수 있는 경우의 수 + z를 하나 줄였을 때 만들 수 있는 경우의 수

이고

1. 만약 a를 하나 줄였을 때 만들 수 있는 경우의 수가 K보다 많다면,

a를 앞에 하나 두고 a를 하나 더 줄였을 때 만들 수 있는 경우의 수를 본다.

 

2. 만약 a를 하나 줄였을 때 만들 수 있는 경우의 수가 K보다 적다면,

그 자리에 z를 넣어야 한다.

왜냐하면 a (xxxx) 보다 z (xxxx)가 사전순으로 더 뒤에 있기 때문에 

부족한 경우의 수를 채울 수 있기 때문이다.

 

3. 하지만 (n+m) C (n) 이 K보다 작다면 -1을 리턴해야 한다.

 

여기에 위 이항 계수 항등식의 2번째 법칙을 조합을 구한다.

조합은 팩토리얼 단위로 커지기 때문에 숫자가 너무 커서 long long으로 

저장해도 부족하다.

간단하게 계산해 봐도 200 C 100 = 200/100 * 199/99 * 198/98 ... 101/1 로 계산해봐도

2^100 이 넘고 100 log2 ~ 280이므로 10^280으로도 어림없다.

 

하지만 K가 1억 개이므로 1억 개를 넘어가는 계산을 할 필요가 없으므로

1억을 넘는 조합의 결과는 전부 1억으로 치환해도 무방할 것이다.

 

고로 combi라는 dfs 함수를 이용하여 dp를 구성하여 사용하면

0ms에 문제가 끝나는 것을 볼 수 있다.

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
#define MAX 1000000000
static int dp[201][201];
int combi(int n, int k) {
	if (n == k || k == 0) {
		dp[n][k] = 1;
		return 1;
	}
	if (dp[n][k] != 0) {
		return dp[n][k];
	}
	else {
		dp[n][k] = combi(n - 1, k - 1) + combi(n - 1, k);
		if (dp[n][k] > MAX ) {
			dp[n][k] = MAX;
		}
        return dp[n][k];
	}
	
}


int main()
{
	int N, M, K;
	cin >> N >> M >> K; // a 수 N z 수 M, K번째 문자열?

	string str;
	while (true) {
		if (N < 0 || M < 0) { break; }
		if (combi(N + M - 1, N - 1) == MAX) {
			str += "a";
			N -= 1;
			continue;
		}
		if (combi(N + M - 1, N - 1) + combi(N + M - 1, N) < K) { cout << -1; return 0; }
		if (combi(N + M - 1, N - 1) >= K) // a 가 먼저 앞에 나오는 경우
		{
			str += "a";
			N -= 1;

		}
		else //z가 나오는 경우
		{
			str += "z";
			K -= combi(N + M - 1, N - 1);
			M -= 1;
		}
        
		if (K == 1) {
			for (int i = 0; i < N; i++)
				str += "a";

			for (int i = 0; i < M; i++)
				str += "z";
			cout << str;
			return 0;
		}

	}
	cout << str;


}