1256 사전 (조합론) [Gold II]

1256번: 사전 (acmicpc.net)

 

N개의 'a'와 M개의 'z'로 이루어진 문자열들이 알파뱃 순서로 정렬되어있을때

K번째의 문자열을 찾는 문제입니다.

 

풀이법

예시 N = 2, M = 2, K = 6 이라고 할때의 풀이법

 

a, z가 맨 앞에 올 때의 경우의 수

// a a z z
// a z a z  
// a z z a   

// z a a z  
// z a z a
// z z a a

a이 맨 앞에 올 때의 경우의 수는 3개

z이 맨 앞에 올 때의 경우의 수도 3개

문제는 6번째의 문자열을 찾기 때문에 a가 맨 앞에 올 수 없기에 z를 출력해줌

경우의 수 3개를 건너 뛰었기 때문에 K에도 3을 빼줌

 

// z   a a z  
// z   a z a

// z   z a a

a이 맨 앞에 올 때의 경우의 수는 2개

z이 맨 앞에 올 때의 경우의 수는 1개

 

K는 3이기 때문에 a를 두 번째 수에 넣을 수 없음

다시 한번 z를 출력하고 k에 경우의 수 2를 빼줌

// z z  a a

a이 맨 앞에 올 때의 경우의 수는 1개

z이 맨 앞에 올 때의 경우의 수는 0개

 

K = 1이기 때문에 a를 넣을 수 있음 a 출력

 

// z z a   a

 

a이 맨 앞에 올 때의 경우의 수는 1개

z이 맨 앞에 올 때의 경우의 수는 0개

 

K = 1이기 때문에 a를 넣을 수 있음 a 출력

끝

 

 

이런 방식으로 경우의 수를 찾고 K와 비교하여 문자를 출력해주면 됩니다

 

경우의 수 찾는 방법

a가 맨 앞에 올 때의 경우의 수는 

맨 앞에 올 a를 제외한 수 (3) 중에 z의 수 (2)혹은 a의 수 -1 (1)을 선택할 경우의 수와 같습니다

그렇기에 이항계수 구하는 법과 동일하게 경우의 수를 미리 구해놓으면 쉽게 풀 수 있게됩니다

이항계수 구하기

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

static int N, M, K;
static long C[202][202];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); 
	cout.tie(NULL);

	// N개의 a, M개의 z
	cin >> N >> M >> K;
	
	for (int i = 0; i <= 200; i++) {
		C[i][i] = 1;
		C[i][0] = 1; 
		C[i][1] = i; 
	} 
	for (int i = 3; i <= 200; i++) { 
		for (int j = 2; j <= i; j++) { 
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j];  
			if (C[i][j] > 1000000000)
				C[i][j] = 1000000001;
		}
	}

	if (C[N + M][M] < K) {
		cout << "-1";
		return 0;
	}

	vector<char> result;
	int k = K;
	while (N + M) { 
		// n이 앞 나올 경우의 수 
		long n = C[N - 1 + M][M];   

		if (k <= n) {  
			result.push_back('a');
			N--;
		}  
		else {
			result.push_back('z');
			M--; 
			k -= n;
		}  
	}

	for (char r : result)
		cout << r; 

}