[DFS 중복조합] 백준 15652 N과 M(4) / 15658 N과 M(8) C++

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

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

15652번: N과 M (4)

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

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

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/15658

15658번: 연산자 끼워넣기 (2)

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대

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

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