Algorithm/BOJ
[BOJ]15657번: N과 M (8) (c++)
HBGB
2020. 5. 6. 22:21
https://www.acmicpc.net/problem/15657
15657번: N과 M (8)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
www.acmicpc.net
|
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
50
|
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 8;
int numbers[MAX];
int output[MAX];
void dps(int N, int M, int depth, int start)
{
if (depth == M)
{
for (int i = 0; i < M; ++i)
{
cout << output[i] << ' ';
}
cout << '\n';
return;
}
// 비내림차순, 중복허용
for (int i = start; i < N; ++i)
{
output[depth] = numbers[i];
dps(N, M, depth + 1, i);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
for (int i = 0; i < N; ++i)
{
cin >> numbers[i];
}
// 정렬
sort(numbers, numbers + N);
dps(N, M, 0, 0);
return 0;
}
Colored by Color Scripter
|