[BOJ C++] 백준 15657번: N과 M (8)

 📚 문제

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

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• N과 M 시리즈는 조건에 만족하는 수열을 모두 출력하는 문제이다. 확률과 통계에서 배우는 순열, 조합, 중복순열, 중복조합을 구현한다고 생각하면 된다.
• 이번 N과 M (8)은 N과 M (1)~(4)와 달리 입력 받은 N개의 숫자로 길이가 M인 수열을 만드는 문제이다. 입력 받은 숫자는 num 배열에 저장하였고, 사전 순으로 수열을 만들어야 하므로 오름차순으로 정렬하였다. 이 문제는 N과 M (4)와 똑같이 구현하되, 반복문에서 숫자 i 대신 배열에 저장해두었던 num[i]를 사용하면 해결할 수 있다.
• N과 M (5)와 달리 중복된 숫자도 허용한다. 즉, 방문 여부를 확인할 필요가 없으므로 visited 배열이 필요하지 않다. 또, N과 M (6)과 유사하게 비내림차순을 만족해야한다. 즉, N과 M (4), N과 M (6) 문제를 변형하고, 조건을 조금만 추가하면 쉽게 해결할 수 있다.
• [BOJ C++] 백준 15652번: N과 M (4)
• [BOJ C++] 백준 15655번: N과 M (6)
• 재귀함수(DFS)와 백트래킹 방식을 사용하여 구현한다. 자세한 구현 방법은 다음과 같다.

 

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

 

• 반복문을 통해 num[0]부터 num[N-1]까지 숫자를 순회한다. 이번 문제에서는 숫자를 중복하여 사용할 수 있으므로 별다른 조건 없이 arr[dep]에 num[i]를 바로 추가할 수 있지만, 비내림차순을 만족해야하므로 배열에 이미 저장되어 있는 수보다 큰 수만 저장할 수 있다. 따라서 num[i]가 arr[dep-1]보다 큰 숫자라면 arr[dep]에 num[i]를 추가한다.
• arr 배열에 채운 수열의 길이가 M이 되면 모두 출력한 뒤 종료(return)한다.

---

 ⌨️ C++ 코드

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

int n, m;
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 (num[i] >= arr[dep - 1]) {
      arr[dep] = num[i];
      dfs(dep + 1);
    }
  }
}

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);
  }
  sort(num.begin(), num.end());

  dfs(0);
}