N과M (9)

• N과M 시리즈 중 생각이 좀 필요했던 문제

코드

[ 백트래킹 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int N, M;
int arr[10];
int isused[10];
vector<int> save(10);
void func(int depth){
    if(depth == M){
        for(int i=0;i<M;i++)
            cout << arr[i] <<' ';
        cout << '\n';
    }else{
        /* pre는 지역변수여야함, 전역변수가되면 시작이 다른 수열에도
        영향을 준다. */
        int pre=-1;
        for(int i=0;i<N;i++)
        {
            if(isused[i]) continue;
            if(save[i] == pre) continue;
            isused[i] = true;
            arr[depth] = save[i];
            pre = save[i];
            func(depth+1);
            isused[i] = false;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
        cin >> save[i];

    sort(save.begin(), save.begin()+N);
    func(0);
    return 0;
}

• key point!
  : 시작이 같은 수열에서 같은 값을 출력하지 않게 조건을 만들어야 한다
  (sort하고 func실행하기 때문에 바로 이전값을 저장하는 변수를 써야함 prev)

---

[ next_permutation 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int N, M;
int arr[10];
vector<int> save(10);
vector<vector<int>> ans;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
        cin >> save[i];
    sort(save.begin(), save.begin()+N);
    fill(arr, arr+N, 1);
    for(int i=0;i<M;i++) arr[i] = 0;
    do{
        vector<int> tmp;
        for(int i=0;i<N;i++)
            if(!arr[i])
                tmp.push_back(save[i]);
        do{
            ans.push_back(tmp);
        }while(next_permutation(tmp.begin(), tmp.end()));
    }while(next_permutation(arr, arr+N));

    sort(ans.begin(), ans.end());
    for(int i=0;i<ans.size();i++)
    {
        bool result = true;
        if(i>0){
            for(int j=0;j<ans[i].size();j++)
            {
                if(ans[i-1][j] != ans[i][j]) result = false;
            }
        }
        if(i == 0 or !result){
            for(int j=0;j<ans[i].size();j++)
            {
                cout << ans[i][j] << ' ';
            }
            cout << '\n';
        }
    }
    return 0;
}

• 로직
  1) 2중 do~while()로 N개중 M개를 뽑는 모든 조합을 구한다
  2) ans를 정렬한뒤, 바로 이전 수열과 같지 않으면 출력한다! (i==0일때 예외처리)