알고리즘 /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;
}