15657번: N과 M (8)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열
www.acmicpc.net
N과M 8번째 문제입니다.
배열에서 M개를 고른 수열을 구하는데
같은 수를 여러번 사용해도되며 비내림차순으로 이루어진 수열이어야 합니다.
중복이 가능하기 때문에 방문체크는 하지않고,
비내림차순이므로 dfs를 돌리는 과정에서 ans에 추가했던 인덱스를 +1하지 않고 그대로 재귀로 보내버리는 식으로 하였습니다.
|
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
51
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static ArrayList<Integer> list, ans;
static int N, M;
static void dfs(int idx, int cnt) {
if (cnt == M) {
for (int i = 0; i < ans.size(); i++) {
sb.append(ans.get(i) + " ");
}
sb.append("\n");
return;
}
for (int i = idx; i < N; i++) {
int x = list.get(i);
ans.add(x);
dfs(i, cnt + 1);
ans.remove(cnt);
}
}
static void input() throws Exception {
list = new ArrayList<>();
ans = new ArrayList<>();
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
Collections.sort(list);
}
public static void main(String[] args) throws Exception {
input();
dfs(0, 0);
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 15664 N과 M (10) (0) | 2021.01.30 |
|---|---|
| boj 15663 N과 M (9) (0) | 2021.01.28 |
| boj 15656 N과 M (7) (0) | 2021.01.27 |
| boj 15655 N과 M (6) (0) | 2021.01.27 |
| boj 15654 N과 M (5) (0) | 2021.01.27 |