백준 s3 15650 N과 M (2) c++

https://acmicpc.net/problem/15650

15650번: N과 M (2)

 

코드 - 재귀로 푼 버전

/*boj s3 15650 N과 M (2)*/
#include <iostream>
#define MAXN 9
using namespace std;

int N, M;
int answer[MAXN];

void func(int k, int i) { // i부터 시작
    if (k == M) {
        for (int i = 0; i < M; i++) {
            cout << answer[i] << " ";
        }
        cout << '\n';
        return;
    }

    for (int j = i; j <= N; j++) {
        answer[k] = j;
        func(k + 1, j + 1);
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;

    func(0, 1);
}

 

 

코드 - next_permutation으로 푼 버전

/*boj s3 15650 N과 M (2) next_perm*/
#include <algorithm>
#include <iostream>
#include <vector>
#define MAXN 105
using namespace std;

int N, M;
vector<int> choice;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        if (i < M)
            choice.push_back(0);
        else
            choice.push_back(1);
    }

    do {
        for (int i = 0; i < N; i++) {
            if (choice[i] == 0)
                cout << i + 1 << " ";
        }
        cout << "\n";
    } while (next_permutation(choice.begin(), choice.end()));
}

 

 

next_permutation

오름차순으로 정렬되어 있을 때, 조합을 구해준다.

N개 중 M개를 택하려면, {0, 0, 0, 1, 1} 조합으로 5개 중 3개를 택하는 조합을 구할 수 있다.