알고리즘 /Backtracking
[백준] N과 M (7)_15656, N과 M (8)_15657
장주아
2020. 3. 9. 02:41
N과 M (7)
N개 중에 M개를 고르는데, N개의 자연수는 모두 다른 수이고, 같은 수를 여러 번 골라도 된다.
사전 순으로 증가하는 순서로 출력해야 한다.
사전 순으로 출력하기 위해서 정렬을 해주면 된다.
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
|
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
int arr[7], s[7];
void dfs(int cnt) {
if (M == cnt) {
for (int i = 0; i < M; i++) {
cout << s[i] << " ";
}
cout << "\n";
return;
}
for (int i = 0; i < N; i++) {
s[cnt] = arr[i];
dfs(cnt + 1);
}
}
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
sort(arr, arr + N);
dfs(0);
return 0;
}
|
N과 M (8)
8번 문제는 7번에서 비내림차순이어야 한다는 조건이 추가됐다.
if (cnt != 0 && s[cnt - 1] > arr[i]) continue;
이 조건을 추가하여 비내림차순이 아니라면 수열을 만들지 않고 넘어간다.
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
|
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
int arr[8], s[8];
void dfs(int cnt) {
if (cnt == M) {
for (int i = 0; i < M; i++) {
cout << s[i] << " ";
}
cout << "\n";
return;
}
for (int i = 0; i < N; i++) {
if (cnt != 0 && s[cnt - 1] > arr[i]) continue;
s[cnt] = arr[i];
dfs(cnt + 1);
}
}
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
sort(arr, arr + N);
dfs(0);
return 0;
}
|