[5일차] 조합론 D - 1256 : 사전

골드 Ⅲ

 

#include <iostream>
#define MAXK 1000000000
using namespace std;

int N, M, K;
int nCm[201][201];

void solve(int l, int m, int k) {
	if (l == 0) return;

	if (nCm[l -1][m] < k) {
		printf("z");
		return solve(l - 1, m - 1, k - nCm[l - 1][m]);
	}
	else {
		printf("a");
		return solve(l - 1, m, k);
	}
}

int main() {
	scanf("%d%d%d", &N, &M, &K);
	for (int i = 0; i <= 200; i++) {
		for (int j = 0; j <= i; j++) {
			if (i == 0 || j == 0) nCm[i][j] = 1;
			else {
				nCm[i][j] = nCm[i - 1][j - 1] + nCm[i - 1][j];
				if (nCm[i][j] > MAXK) nCm[i][j] = MAXK + 1;
			}
		}
	}
	if (K > nCm[N + M][M]) printf("-1");
	else solve(N + M, M, K);
}

 

사전순으로 정렬을 해놓으면... 쭉 될테니까

그 사전순으로 정렬 한 곳에서 k번째를 찾는다고 생각을 하기

(사전순으로 k번째까지 하나씩 정렬을 해보는게 아니라.. 이미 그런 정렬이 있다고 치고 거기서 k번째를 찾는다고 생각)

 

사전순으로 정렬을 쭉 해놓으면.. 총 개수는 n+mCm이 되겠지?? n+mCn이라고 봐도 되고..

 

그러면 일단.. 첫번째 문자를 a로하냐 z로 하냐에 따라서 이 문자열이

a로 할 경우 : 정렬에서 1번째 ~ n+m-1Cm 번째 인덱스 사이에 있겠고

z로 할 경우 : 정렬에서 n+m-1Cm-1 ~ n+mCn번째 인덱스 사이에 있겠지??

 

K가 어느 범위에 들어가는지 보면서... 그렇게 k번째를 찾기...........