[백준] 15663.cpp : N과 M (9)

www.acmicpc.net/problem/15663

15663번: N과 M (9)

---

• 기존의 문제와 똑같은 방식을 적용한다.
• 다만 기존에 뽑았던 수열과 중복되는 수열은 출력하면 안되기 때문에, 뽑았던 수열들에 대한 정보를 저장해 놓고, 현재 수열을 출력하기 전에 모든 수열들과 비교해보는 방식을 추가한다.
• 위와 같은 풀이 방식은 굉장히 비효율적인 방법이다.
• 값을 저장할 때 해시를 사용하거나, 직전 자릿수의 값을 비교하는 방식으로 푸는 것이 더 깔끔하다.

---

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

using namespace std;

int n, m;
vector<int> arr(8, 10001);
vector<int> ans(8, 0);
vector<bool> visited(8, false);
vector<vector<int>> bef;

bool exist()                                        // 기존에 뽑았던 수열들 중에 현재 수열이 있는지 확인하는 함수
{
    for(int idx = 0 ; idx < bef.size() ; idx++)     // 기존 수열들 완전탐색
    {
        bool same = true;
        for(int i = 0 ; i < m ; i++)
        {
            if(bef[idx][i] != ans[i])               // 만약 다른게 한개라도 있으면 same 은 false
            {
                same = false;
                break;
            }
        }
        if(same) return true;                       // 수열의 모든 원소가 같다면 true 를 반환
    }
    return false;
}

void check(int cur, int size)
{
    if(size == m)
    {
        if(exist()) return;                         // 만약 기존 수열에 이미 존재한다면 그냥 종료
        for(int i = 0 ; i < m ; i++)                // 그 외에는
        {
            cout << ans[i] << " ";                  // 출력해주고
        }
        cout << '\n';
        bef.push_back(ans);                         // 뽑은 수열 목록에 현재 수열도 추가
        return;
    }
    for(int i = 0 ; i < n ; i++)
    {
        if(visited[i] == false)
        {
            visited[i] = true;
            ans[size] = arr[i];                     // 현재 자릿수를 넣어주고
            check(i, size + 1);                     // 다음 자릿수 재귀호출
            visited[i] = false;
        }
    }
}

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

    check(-1, 0);
}