15663 N과 M (9)

15663 N과 M (9) (c++)

문제

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

접근 방식

Backtracking

1. 길이가 M인 수열
2. 중복 X
3. 수열은 사전 순으로 오름차순으로 출력

수열을 우선 정렬하여 백트래킹 했을 때, 사전 순으로 오름차순이 되게 만듦
중복을 없애기 위해 vector를 원소로 가지는 Set을 활용 백트래킹을 하다가 벡터의 길이가 M이 되었을 때 set에 넣어주고, 백트래킹이 완료되면 set의 원소들을 출력

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int N, M;
vector<int> arr, target;

set<vector<int>> s;

void BT()
{
    if (target.size() == M)
    {
        s.insert(target);
        return;
    }

    for (int i = 0; i < arr.size(); ++i)
    {
        target.push_back(arr[i]);
        arr.erase(arr.begin() + i);
        BT();
        arr.insert(arr.begin() + i, target.back());
        target.pop_back();
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M;
    arr = vector<int>(N);

    for (int i = 0; i < N; ++i)
    {
        cin >> arr[i];
    }

    sort(arr.begin(), arr.end());

    BT();

    for (vector<int> v : s)
    {
        for (int i = 0; i < v.size(); ++i)
        {
            cout << v[i] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

다시 생각해 볼 점

1. 중복을 없앨 때는 Set 자료구조를 사용하는게 좋다.
2. N개 중 M개를 선택하는 수열 문제는 백트래킹을 활용하면 된다.
3. 사전 순으로 오름차순을 만들기위해 백트래킹 전 int 들을 정렬해줬다.