백준 15663 N과 M(9)

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

 

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

using namespace std;

vector<int> arr;
vector<int> ans;

bool visit[10];

int n, m;

void dfs(int cnt) {

    if (cnt == m) {
        for (int i=0;i<m;i++) {
            cout << ans[i] << " ";
        }
        cout << "\n";

        return;

    }

    int temp = 0;

    for (int i = 0; i < n; i++) {
        if (!visit[i] && temp != arr[i]) {
            ans[cnt] = arr[i];
            temp = ans[cnt];
            visit[i] = true;
            dfs(cnt + 1);
            visit[i] = false;
        }
    }


}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    cin >> n >> m;

    arr.resize(n);
    ans.resize(n);

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

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

    dfs(0);

    return 0;
}

 

 백트래킹 문제이다.

 다른 n과 m 문제와 달리 같은 수열을 처리하는 것이 관건이다.

풀이 

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

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

 

 배열을 입력받고, 정답이 사전 증가 순으로 출력되어야 하므로 정렬한다.

void dfs(int cnt) {

    if (cnt == m) {
        for (int i=0;i<m;i++) {
            cout << ans[i] << " ";
        }
        cout << "\n";

        return;

    }

    int temp = 0;

    for (int i = 0; i < n; i++) {
        if (!visit[i] && temp != arr[i]) {
            ans[cnt] = arr[i];
            temp = ans[cnt];
            visit[i] = true;
            dfs(cnt + 1);
            visit[i] = false;
        }
    }


}

 

 이 문제는 중복된 수열을 허용하지 않는 것이 관건이다. 다음 입력이 주어졌다고 하자.

1 2 3 4 4

 

 현재 수열이 3 2 라고 가정할 때 다음에 들어갈 수 있는 숫자는 1, 4, 4이다. 여기서 4는 중복되므로 한 번만 출력한다. 즉, 같은 깊이에서의 중복만 체크한다면 중복된 수열을 처리할 수 있다. 이런 식으로 숫자를 조합하여 주어진 길이인 m에 도달했을 경우 그 배열을 출력하면 정답을 구할 수 있다.