수열

수 또는 다른 대상의 순서있는 나열

나열 순서를 생각해야 하며
중복이 허용된다.

그렇다면 문제의 조건을 보자

N개의 자연 수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이여야 한다.

비내림차순 == 오름차순?

비내림차순은 점점 증가하는 수열이다.

오름차순과 같아 보이겠지만 오름차순은 인접한 두 수가 같을 수도 있는지 여부를 명확하게 알려주지 않지만 비내림차순은 같을 수도 있음을 명확히 해준 것

이런 경우를 위해 명시해준 것이 아닐까... 한다.

1 1 1 1 > 비내림차순이지만 과연 오름차순일까
1 2 3 4 > 비내림차순이고 오름차순

구현

들어온 수열 정렬
맨 앞칸부터 채우기
다 채우면 출력

간단하지만 수열의 중복과 순서에 대한 조건이 있기 때문에 적절하게 처리해주어야 한다.

void seq(int x, int len)
{
    if (M == len) // 길이를 다 채우면
    {
        print(); // 출력
        return;
    }
    else
    {
        int temp = 0; // 이전값을 저장할 변수
        for (int i = x; i < v.size(); i++)
        {
            if (v[i] != temp) // 이전값과 다르다면
            {
                ans[len] = v[i];
                print();
                temp = ans[len];
                seq(i, len+1); // 현재 탐색 위치부터 시작할 수 있도록 i값을 넣어준다.
            }
        }
    }
}

이전 값과 같다면 수열의 중복이 발생하기 때문에 조건을 넣어줌

조건이 없다면?

input
4 2 9 7 9 1
output
1 0 1 1 1 1 // 중복 1 7 1 7 // 중복 1 9 1 9 7 9 7 7 7 7 7 9 7 9 9 9 9 9 // 이렇게 중복이 발생한다. 9 9

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int>v;
int ans[9] = {0, };
int pre[9] = {0, };
int N, M;

void print(void)
{
    for (int i = 0; i < M; i++)
        cout << ans[i] << " ";
    cout << '\n';
}

void seq(int x, int len)
{
    if (M == len)
    {
        print();
        return;
    }
    else
    {
        int temp = 0;
        for (int i = x; i < v.size(); i++)
        {
            if (v[i] != temp)
            {
                ans[len] = v[i];
                print();
                temp = ans[len];
                seq(i, len+1);
            }
        }
    }
}

void input(void)
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        int x;
        cin >> x;
        v.push_back(x);
    }
}

void vPrint(void)
{
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << " ";
    cout << '\n';
}

int main(void)
{
    input();
    sort(v.begin(), v.end());
    seq(0, 0);
}