백준 15663번 [N과 M (9)](C++)-yes6686- 티스토리

백준 문제 풀이: 15663 [N과 M (9)]

---

문제 링크: https://www.acmicpc.net/problem/15663

문제 설명:

1부터 N까지 자연수 중에서 M개를 고른 수열을 출력하는 문제입니다. 입력으로 주어지는 N개의 숫자 중 M개를 고르며, 수열은 사전순으로 증가하는 순서로 출력해야 합니다. 같은 숫자가 여러 번 입력될 수 있으므로, 중복된 순열은 제거해야 합니다.

입력:

• 첫째 줄에 자연수 N과 M이 주어집니다. (1 ≤ M ≤ N ≤ 8)
• 둘째 줄에 N개의 자연수가 주어집니다. (1 ≤ arr[i] ≤ 10,000)

출력:

• 한 줄에 하나씩 조건을 만족하는 수열을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int arr[8];
bool visited[8];
int result[8];

void DFS(int depth) {
    if (depth == m) {
        for (int i = 0; i < m; i++) {
            cout << result[i] << ' ';
        }
        cout << '\n';
        return;
    }

    int last_used = -1; // 이전에 사용한 값 저장

    for (int i = 0; i < n; i++) {
        if (!visited[i] && arr[i] != last_used) {
            visited[i] = true;
            result[depth] = arr[i];
            last_used = arr[i]; // 중복된 값 방지
            DFS(depth + 1);
            visited[i] = false;
        }
    }
}

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

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

    sort(arr, arr + n); // 입력 정렬
    DFS(0);

    return 0;
}

예제

입력:
4 2
9 7 9 1

출력:
1 7
1 9
7 9
9 9

---

코드 설명

• 입력 정렬:
  • 입력 배열을 정렬하여 사전순으로 출력이 가능하도록 합니다.
• DFS 탐색:
  • 현재까지 선택된 숫자를 저장하는 배열 result를 사용합니다.
  • 숫자를 선택할 때, 이미 사용된 숫자는 visited 배열로 체크하여 중복을 방지합니다.
• 중복 제거:
  • 각 DFS 단계에서 이전에 사용된 값을 last_used에 저장하여 같은 값을 반복적으로 선택하지 않도록 합니다.

시간 복잡도

• DFS의 시간 복잡도는 O(N!/(N-M)!)이며, 최대 N이 8이므로 충분히 처리 가능합니다.

---

결과

코드는 주어진 조건을 만족하며, 입력된 숫자로 사전순으로 정렬된 모든 고유한 수열을 정확히 출력합니다. 중복 제거를 효율적으로 처리하였습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!