[BOJ] 1256 사전

Time Lapse :1hour 14min 22sec

1256.cpp

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
#include <iostream>
#include <algorithm>
#define ull unsigned long long
using namespace std;
int a, z, k;
ull comb[201][101];
ull combination(int n, int m) {
return !n || !m ? 1 : comb[n+m][m] ? comb[n+m][m] : comb[n+m][m] = combination(n-1,m) + combination(n,m-1);
}
void dfs(int n, int m, int cur) {
if(!n) {
for(int i = 0; i < m; ++i) printf("z");
exit(0);
}
if(!m) {
for(int i = 0; i < n; ++i) printf("a");
exit(0);
}
if(combination(n-1,m) < cur) {
printf("z");
dfs(n,m-1,cur-combination(n-1,m));
} else {
printf("a");
dfs(n-1,m,cur);
}
}
int main() {
scanf("%d %d %d",&a,&z,&k);
if(combination(a,z) < k){
printf("-1");
exit(0);
}
dfs(a,z,k);
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2020/08/31/PS/BOJ/1256/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.