와이유스토리

[DFS 순열] 백준 15649 N과 M(1) / 15654 N과 M(5) C++ 본문

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

[DFS 순열] 백준 15649 N과 M(1) / 15654 N과 M(5) C++

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

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

 

15649번: N과 M (1)

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

www.acmicpc.net

#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);
}

 

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

 

15654번: N과 M (5)

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

www.acmicpc.net

#include<iostream>

#define MAX 11

using namespace std;

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

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

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);
}

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

[DFS 중복순열] 백준 15651 N과 M(3) / 15656 N과 M(7) C++  (0) 2022.01.22
[DFS 조합] 백준 15650 N과 M(2) / 15655 N과 M(6) C++  (0) 2022.01.22
[DFS 백트래킹] 백준 15684 사다리 조작 C++  (0) 2022.01.22
[DFS 단순 반복, BFS 반복, 크루스칼] 백준 17472 다리 만들기2 C++  (0) 2022.01.22
[DFS 백트래킹] 백준 17136 색종이 붙이기 C++  (0) 2022.01.22
'코딩테스트/그래프|트리' Related Articles more
Comments