[BOJ C++] 백준 15664번: N과 M (10)

 📚 문제

[BOJ C++] 백준 15664번: N과 M (10)
https://www.acmicpc.net/problem/15664

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• N과 M 시리즈는 조건에 만족하는 수열을 모두 출력하는 문제이다. 확률과 통계에서 배우는 순열, 조합, 중복순열, 중복조합을 구현한다고 생각하면 된다.
• 이번 N과 M (10)은 N과 M (1)~(4)와 달리 입력 받은 N개의 숫자로 길이가 M인 수열을 만드는 문제이다. 입력 받은 숫자는 num 배열에 저장하였고, 사전 순으로 수열을 만들어야 하므로 오름차순으로 정렬하였다. 이 문제는 N과 M (5)~(8)과 달리 같은 숫자가 여러 번 입력될 수 있다. 중복 입력된 숫자로 인해 같은 수열이 만들어질 가능성이 있으므로 이를 고려할 수 있는 조건을 추가해야 한다. 여기까지는 N과 M (9)와 유사하지만, 이번 문제는 각 수열이 비내림차순을 만족해야 한다는 조건이 하나 더 추가된다. 이는 N과 M (4)와 유사한 조건을 추가하면 된다. 
• [BOJ C++] 백준 15652번: N과 M (4)
• [BOJ C++] 백준 15663번: N과 M (9)
• 재귀함수(DFS)와 백트래킹 방식을 사용하여 구현한다. 자세한 구현 방법은 다음과 같다.

 

 

• 입력 받은 수를 오름차순으로 정렬한 배열(num), 방문 여부를 체크하는 배열(visited), 선택한 값을 저장하는 배열(arr)을 준비한다. visited[i]는 숫자 num[i]를 선택했는지의 여부를, arr[dep]는 배열의 (dep+1)번째에 삽입될 숫자를 저장한다.
• num 배열의 크기를 미리 지정하지 않고 숫자를 입력 받을 때마다 크기를 늘려나가는 방식으로 구현했다. 배열의 크기를 미리 지정할 경우, 그보다 적은 양의 숫자를 입력 받는다면 남은 배열의 값은 0으로 채워진다. 배열을 그대로 사용한다면 문제가 없겠지만, 오름차순으로 정렬해야 하므로 의미 없는 숫자들이 앞으로 정렬되어 의도한 바와 다른 결과가 나타날 수 있기 때문이다.

 

• 반복문을 통해 num[0]부터 num[N-1]까지 숫자를 순회한다. 이번 문제에서는 숫자를 중복하여 사용할 수 없으므로 현재 숫자가 이미 방문한 숫자가 아닌 경우에만 선택할 수 있다. 또, 비내림차순을 만족해야 하므로 배열에 이미 저장되어있는 수보다 큰 수만 저장할 수 있다. dep=0인 경우에는 num[i]를 바로 추가하고, dep>0인 경우에는 arr[dep-1] <= num[i]인 경우에만 저장한다. 따라서 num[i]가 방문한 적이 없는 숫자이며 arr[dep-1]보다 크거나 같은 숫자라면 visited[i]에 방문 표시를 하고 arr[dep]에 num[i]를 추가한다. 그러나, 같은 숫자가 여러 개 있으므로 중복된 수열이 만들어지진 않는지도 확인해야 한다.

 

 

 

 

• 위 그림을 보면, dep가 같은 곳에 이미 입력 되었던 숫자가 다시 입력되면 중복된 수열이 만들어지는 것을 알 수 있다. 따라서 이전에 입력했던 값을 따로 저장해두었다가 새로운 값을 넣을 때 비교해보고 다른 숫자인 경우에만 수열을 만들어야 한다. cur 배열을 따로 두어 cur[dep]에 최신 값을 저장하는 방식으로 구현하였다. 또, 반복문을 모두 돌고 함수가 종료되기 전에 cur[dep] 값을 0으로 초기화한다.
• arr 배열에 채운 수열의 길이가 M이 되면 모두 출력한 뒤 종료(return)한다.
• 함수가 return된 후에는 다시 해당 숫자를 비방문 처리한다.

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> num;
vector<int> visited;
vector<int> arr(9);
vector<int> cur(9);  // cur[dep]: 수열의 (dep+1)번째에 가장 최근에 들어간 수.

void dfs(int dep) {
    if (dep == m) {
        for (int i = 0; i < m; i++) cout << arr[i] << ' ';
        cout << '\n';
        return;
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i] && cur[dep] != num[i] && (!dep || (dep && arr[dep - 1] <= num[i]))) {
            visited[i] = 1;
            cur[dep] = num[i];
            arr[dep] = num[i];
            dfs(dep + 1);
            visited[i] = 0;
        }
    }
    cur[dep] = 0;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        num.push_back(tmp);
        visited.push_back(0);
    }
    sort(num.begin(), num.end());
    dfs(0);
}