백준1256 사전

작성일 | In

문제 링크

  • http://icpc.me/1256

사용 알고리즘

  • DP

시간복잡도

  • O(n2)

풀이

꽤 자주 출제되는 DP 유형인 k-th lexicographical string 문제입니다.

a를 i개, z를 j개 쓸 수 있는 상황에서 cnt번째 문자열을 출력해야 한다고 가정을 하고, a를 i-1개, z를 j개 사용해서 만들 수 있는 경우의 수를 avail이라고 정의합시다.
만약 avail이 cnt보다 크다면 z를 출력하고, cnt에서 avail을 뺀 뒤 재귀적으로 다시 연산해줍니다. 반대의 경우에는 a를 출력하면 됩니다. 자세한 구현은 코드를 참고해주시기 바랍니다.

a를 n개, z를 r개 사용해서 만들 수 있는 경우의 수는 (n+1)Hr이기 때문에 중복 조합을 구해주면 됩니다. nHr은 (n+r-1)Cr과 동치입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

int n, m, k;
typedef long long ll;

ll c[201][201];
ll lim;

inline ll avail(int a, int b){ return c[a+b][b]; }

void f(int i, int j, int cnt, int len){
	if(len <= 0) return;
	if(i == 0){
		cout << 'z';
		f(i, j-1, cnt-avail(i-1, j), len-1);
	}
	else if(j == 0){
		cout << 'a';
		f(i-1, j, cnt, len-1);
	}

	else if(avail(i-1, j) >= cnt){
		cout << 'a';
		f(i-1, j, cnt, len-1);
	}else{
		cout << 'z';
		f(i, j-1, cnt-avail(i-1, j), len-1);
	}
}

int main(){
	cin >> n >> m >> k;

	c[1][0] = c[1][1] = 1;
	for(int i=2; i<=200; i++){
		for(int j=0; j<=i; j++){
			c[i][j] = min((ll)1e9+7, c[i-1][j] + c[i-1][j-1]);
		}
	}

	lim = avail(n, m);
	if(k > lim){
		cout << -1; return 0;
	}

	f(n, m, k, n+m);
}