백준 15656번: N과 M (7)

 

백준 15656번: N과 M (7)

15656번: N과 M (7)

 

재귀를 이용해서 풀 수 있는 간단한 문제이다.

배열을 입력하고 문제에 맞게 배열 조합들을 출력하면 된다.

문제 조건 중 수열이 사전 순으로 증가해야하기 때문에 정렬을 해야했다.

 

1. 입력한 배열을 오름차순으로 정렬

2. 중복 허용 가능이어서 다른 조건 필요없이 배열 인덱스가 0번째부터 N-1까지 M번 돌 수 있게 작성했다.

3. M까지 재귀로 배열의 숫자 하나하나를 벡터에 넣는다.

4. M만큼 넣었을 때 그 벡터 배열을 출력

5. 출력 후 재귀함수가 반환되고 마지막 호출 부분에서 벡터의 마지막 부분을 pop한다.

 

말로해서 어렵게 느껴지지만 코드를 보면 좀 더 빠르게 이해할 수 있을 것이다.

 

#include<iostream>
#include<algorithm>
#include<vector>
#define MAX_VAL 8
using namespace std;

int N, M;
int arr[MAX_VAL];
vector<int> v;

void recursive(int depth){
    if(depth == M){
        vector<int>::iterator iter = v.begin();
        for(;iter!=v.end();iter++){
            cout << *iter << " ";
        }
        cout << "\n";
        return;
    }
    for(int i = 0; i < N; i++){
        v.push_back(arr[i]);
        recursive(depth+1);
        v.pop_back();
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }
    sort(arr, arr+N);
    recursive(0);
    return 0;
}