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

백준 문제 풀이: 15665 [N과 M (11)]

---

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

문제 설명:

주어진 N개의 자연수 중에서 M개를 뽑아 중복을 허용하여 만들 수 있는 모든 순열을 출력하는 문제입니다.

단, 같은 수열이 여러 번 중복되어 출력되면 안 되므로, 중복을 제거해야 합니다.

---

문제 해결 코드

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

int n, m;
int arr[8];
vector<int> sequence;
set<vector<int>> unique_sequences;

void backtrack(int depth) {
    if (depth == m) {
        if (unique_sequences.find(sequence) == unique_sequences.end()) {
            unique_sequences.insert(sequence);
            for (int num : sequence) {
                cout << num << " ";
            }
            cout << '\n';
        }
        return;
    }

    for (int i = 0; i < n; i++) {
        sequence.push_back(arr[i]);
        backtrack(depth + 1);
        sequence.pop_back();
    }
}

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

    return 0;
}

예제 입력:

3 1
4 4 2

예제 출력:

2
4

---

코드 설명

• 핵심 알고리즘: 백트래킹을 활용하여 중복을 허용한 모든 순열을 생성하면서, set을 사용해 중복을 방지합니다.
• 구현 세부사항:
  • 입력된 배열을 정렬하여 사전순 출력이 보장되도록 합니다.
  • 백트래킹을 수행하면서, 만들어진 수열이 set에 없는 경우 출력하고 저장합니다.
  • 중복된 원소가 존재하는 경우, 중복 수열이 생성되지 않도록 set을 사용합니다.
• 시간 복잡도: O(N^M), 하지만 중복 제거로 인해 실제 실행 시간은 훨씬 단축됨

---

결과

중복을 허용한 모든 순열을 생성하면서도, 중복된 수열을 제거하여 정확한 결과를 출력합니다. 백트래킹을 활용한 중복 처리 연습에 적합한 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!