와이유스토리

[DFS 조합] 백준 15650 N과 M(2) / 15655 N과 M(6) C++ 본문

코딩테스트/그래프|트리

[DFS 조합] 백준 15650 N과 M(2) / 15655 N과 M(6) C++

유(YOO) 2022. 1. 22. 22:22

 

https://www.acmicpc.net/problem/15650

 

15650번: N과 M (2)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

매개변수 사용

#include <iostream>

#define MAX 11

using namespace std;

int n, m;
int answer[MAX];

void sol(int level, int num) {
    if (level == m){
        for (int i = 0; i < m; i++) {
            cout << answer[i] << " ";
        }
        cout << "\n";
        return;
    }
    for (int i = num; i <= n; i++) {
        answer[level] = i;
        sol(level + 1, i + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    sol(0, 1);
}

 

https://www.acmicpc.net/problem/15655

 

15655번: N과 M (6)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

#include<iostream>

#define MAX 11

using namespace std;

int n, m, a;
int answer[MAX];
vector<int> arr;

void sol(int level, int num) {
    if (level == m) {
        for (int i = 0; i < m; i++) {
            cout << answer[i] << " ";
        }
        cout << "\n";
        return;
    }
    for (int i = num; i < n; i++) {
        answer[level] = arr[i];
        sol(level + 1, i + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> a;
        arr.push_back(a);
    }
    sort(arr.begin(), arr.end());

    sol(0, 0);
}

 

 

* 참고

n=4, m=3 출력 시

1 2 3

1 2 4

만 출력

#include <iostream>

#define MAX 11

using namespace std;

int n, m;
int answer[MAX];
bool isused[MAX];

void sol(int level) {
    if (level == m) {
        for (int i = 0; i < m; i++) {
            cout << answer[i] << " ";
        }
        cout << "\n";
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (isused[i]) continue;
        isused[i] = true;
        answer[level] = i;
        sol(level + 1);
        // isused[i] = false;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    sol(0);
}

'코딩테스트 > 그래프|트리' 카테고리의 다른 글

[DFS 중복조합] 백준 15652 N과 M(4) / 15658 N과 M(8) C++  (0) 2022.01.22
[DFS 중복순열] 백준 15651 N과 M(3) / 15656 N과 M(7) C++  (0) 2022.01.22
[DFS 순열] 백준 15649 N과 M(1) / 15654 N과 M(5) C++  (0) 2022.01.22
[DFS 백트래킹] 백준 15684 사다리 조작 C++  (0) 2022.01.22
[DFS 단순 반복, BFS 반복, 크루스칼] 백준 17472 다리 만들기2 C++  (0) 2022.01.22
'코딩테스트/그래프|트리' Related Articles more
Comments