💡 조합론/다이나믹 프로그래밍/수학
Memory 2336KB Time 0ms Code Length 838B
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
49
#include<iostream>
#include<string>
using namespace std;
long long d[201][201] = { 0 };
long long make_d(int i, int j) {
if (i < j) return 0;
if (i < 0 || j < 0) return 0;
if (d[i][j] == 0) {
d[i][j] = make_d(i - 1, j) + make_d(i - 1, j - 1);
if (d[i][j] > 1000000000) d[i][j] = 1000000000; // 범위 초과...
}
return d[i][j];
}
int N, M, K;
void init() {
cin >> N >> M >> K;
}
string solve() {
string result;
while (1) {
if (N == 0) break;
long long criteria = make_d(N + M - 1, M);
if (K > criteria) {
result += 'z';
K -= criteria;
M--;
}
else {
result += 'a';
N--;
}
}
for (int i = 0; i < M; i++) {
result += 'z';
}
return result;
}
int main() {
init();
d[0][0] = 1;
long long max = make_d(N + M, N);
if (max < K) {
cout << "-1" << '\n';
return 0;
}
cout << solve() << '\n';
}
이 코드는 주어진 N, M, K에 대해 문자열을 생성하는 프로그램이다. make_d 함수는 다이나믹 프로그래밍을 사용하여 이항 계수를 계산한다. solve 함수는 주어진 조건에 따라 문자열을 만들어내는 역할을 한다. main 함수에서는 입력을 받고, make_d 함수를 호출하여 최대값을 계산한 후 solve 함수를 호출하여 결과를 출력한다.
