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

백준 문제 풀이: 15664 [N과 M (10)]

---

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

문제 설명:

주어진 N개의 자연수 중에서 M개를 고른 비내림차순인 수열을 모두 출력하는 문제입니다. 단, 중복되는 수열은 한 번만 출력해야 합니다.

즉, 중복되는 원소가 존재하므로, 같은 조합이 여러 번 나올 수 있지만 이를 제거해야 합니다.

---

문제 해결 코드

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

int n, m;
int arr[9]; // 입력된 숫자 저장
vector<int> seq; // 선택된 숫자 저장
vector<vector<int>> results; // 결과 저장

// 백트래킹 함수
void backtrack(int start, int depth) {
    if (depth == m) {
        results.push_back(seq);
        return;
    }

    int prev = -1; // 이전 값 저장 (중복 방지)
    for (int i = start; i < n; i++) {
        if (arr[i] != prev) { // 같은 값을 중복해서 선택하지 않도록 방지
            seq.push_back(arr[i]);
            backtrack(i + 1, depth + 1);
            seq.pop_back();
            prev = arr[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);

    // 백트래킹 실행
    backtrack(0, 0);

    // 결과 출력
    for (auto &vec : results) {
        for (int num : vec) {
            cout << num << " ";
        }
        cout << '\n';
    }

    return 0;
}

예제 입력:

4 2
9 7 9 1

예제 출력:

1 7
1 9
7 9
9 9

---

코드 설명

• 핵심 알고리즘: 백트래킹을 사용하여 중복되지 않는 조합을 생성합니다.
• 구현 세부사항:
  • 입력된 배열을 정렬하여 비내림차순을 보장합니다.
  • 이전 선택한 값과 현재 값을 비교하여 중복 조합을 방지합니다.
  • start 인덱스를 사용하여 중복 선택을 방지하며 조합을 생성합니다.
• 시간 복잡도: O(N! / (M!(N-M)!)), 조합 생성 및 중복 방지를 고려한 탐색

---

결과

중복을 제거한 비내림차순의 조합을 정확히 출력합니다. 백트래킹을 활용하여 최적의 탐색을 수행하는 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!