[BOJ/백준 15657][C++] N과 M (8)

문제

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

백준 15657

 

문제 내용

입력받은 N개의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다.

이때 고르는 자연수는 서로 중복이어도 상관없으나, 비내림차순 수열이어야 한다

길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

문제 풀이

N과 M (7)과 다르게 N과 M (8)는 수열이 비내림차순이어야 한다는 조건이 추가되었다.

따라서, N과 M (6)처럼 이전에 어떤 값을 선택했는지도 같이 인자로 넘겨주어야 한다.

또한, N과 M (7)처럼 원소의 중복을 허용하기 때문에 used 배열을 쓸 이유가 없다.

[BOJ/백준 15655][C++] N과 M (6)

[BOJ/백준 15654][C++] N과 M (7)

 

코드

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int n, m;

vector<int> result(7, 0);
vector<int> arr;

void back(int cnt, int before_idx) {
    if (cnt == m) {
        for (int i = 0; i < m; i++) {
            cout << result[i] << ' ';
        }
        cout << '\n';
        return;
    }

    for (int i = before_idx; i < n; i++) {
        result[cnt] = arr[i];
        back(cnt + 1, i);
    }
}

int main() {
    cin >> n >> m;
    arr.assign(n, 0); // 여기서 초기화를 크기 n만큼 초기화를 할 것

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

    back(0, 0);
}

 

문제 코드 설명

N과 M (6)과 달리 중복이 허용되기 때문에, back() 함수 안의 for문을 before_idx로 시작해도 되고, main()에서도 -1이 아닌 0으로 인자를 넘겨도 된다.