[BOJ C++] 백준 15655번: N과 M (6)

 📚 문제

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

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• N과 M 시리즈는 조건에 만족하는 수열을 모두 출력하는 문제이다. 확률과 통계에서 배우는 순열, 조합, 중복순열, 중복조합을 구현한다고 생각하면 된다.
• 이번 N과 M (6)은 N과 M (1)~(4)와 달리 입력 받은 N개의 숫자로 길이가 M인 수열을 만드는 문제이다. 입력 받은 숫자는 num 배열에 저장하였고, 사전 순으로 수열을 만들어야 하므로 오름차순으로 정렬하였다. 이 문제는 N과 M (2)와 똑같이 구현하되, 반복문에서 숫자 i 대신 배열에 저장해두었던 num[i]를 사용하면 해결할 수 있다.
• 또, N과 M (5)과 달리 만들어진 각각의 수열 또한 오름차순을 만족해야 하므로 이미 배열에 저장된 수와 비교했을 때 더 큰 수만 그 뒤에 저장할 수 있다. 즉, num[i]가 arr[dep-1]보다 크며 방문한 적이 없는 숫자라면 visited[i]에 방문 표시를 하고 arr[dep]에 num[i]를 추가한다.
• [BOJ C++] 백준 15650번: N과 M (2)
• [BOJ C++] 백준 15654번: N과 M (5)
• 재귀함수(DFS)와 백트래킹 방식을 사용하여 구현한다. 자세한 구현 방법은 다음과 같다.

 

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

 

• 반복문을 통해 num[0]부터 num[N-1]까지 숫자를 순회한다. 이번 문제에서는 숫자를 중복하여 사용할 수 없으므로 현재 숫자가 이미 방문한 숫자가 아닌 경우에만 선택할 수 있다. 또, 오름차순을 만족해야 하므로 배열에 이미 저장되어 있는 수보다 큰 수만 저장할 수 있다. 따라서 num[i]이 arr[dep-1]보다 크며 방문한 적이 없는 숫자라면 visited[i]에 방문 표시를 하고 arr[dep]에 num[i]를 추가한다.
• arr 배열에 채운 수열의 길이가 M이 되면 모두 출력한 뒤 종료(return)한다.
• 함수가 return된 후에는 다시 해당 숫자를 비방문 처리한다.

---

 ⌨️ C++ 코드

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

int n, m;
vector<int> visited;
vector<int> num;
vector<int> arr(9);

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] && (num[i] > arr[dep - 1])) {
      visited[i] = 1;
      arr[dep] = num[i];
      dfs(dep + 1);
      visited[i] = 0;
    }
  }
}

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

  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);
}