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

백준 문제 풀이: 15666번 [N과 M (12)]

---

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

문제 설명:

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];
int result[8];

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

    int last_used = -1;
    for (int i = start; i < n; i++) {
        if (arr[i] != last_used) {
            last_used = arr[i];
            result[depth] = arr[i];
            DFS(depth + 1, i); // 같은 수 선택 가능
        }
    }
}

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, 0);

    return 0;
}

예제

입력:
4 2
9 7 9 1

출력:
1 1
1 7
1 9
7 7
7 9
9 9

---

코드 설명

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

시간 복잡도

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

---

결과

코드는 주어진 조건을 만족하며, 입력된 숫자로 사전순으로 정렬된 모든 수열을 정확히 출력합니다. 중복 제거와 중복 선택 허용 조건을 효과적으로 구현하였습니다.

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