길이가 K인 수열 A가 있을 때, A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하는 비내림차순 수열을 모두 구해야 한다.
같은 수를 여러번 골라도 되므로 코드는 3번 문제와 거의 유사하고, 비내림차순 수열을 만들기 위해서 다음과 같은 부분을 추가했다.
if(!v.empty()) {
if (v[v.size() - 1] > i + 1) {
continue;
}
}
v에 이미 자연수가 들어가 있다면, 새로 넣으려는 수와 v의 마지막 요소를 비교한다. v의 마지막 요소가 더 크다면 비내림차순 수열이 아니므로 그냥 패스한다.
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
|
#include <iostream>
#include <vector>
using namespace std;
int M, N;
vector<int> v;
void print() {
for (int i = 0; i < M; i++) {
cout << v[i] << " ";
}
cout << "\n";
}
//길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK
void dfs(int cnt) {
if (cnt == M) {
print();
return;
}
for (int i = 0; i < N; i++) {
if(!v.empty()) {
if (v[v.size() - 1] > i + 1) {
continue;
}
}
v.push_back(i+1);
dfs(cnt + 1);
v.pop_back();
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> N >> M;
v.clear();
dfs(0);
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
'알고리즘 > Backtracking' 카테고리의 다른 글
[백준] N과 M (6)_15655 (0) | 2019.08.12 |
---|---|
[백준] N과 M (5)_15654 (0) | 2019.08.12 |
[백준] N과 M (3)_15651 (0) | 2019.08.12 |
[백준] N과 M (2)_15650 (조합) (0) | 2019.08.09 |
[백준] N과 M (1)_15649 (순열) (0) | 2019.08.09 |