백준 15651 N과 M (3) | 중복순열 | C++

 

 

이번 포스팅은 백준 15651번 N과 M (3)입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/15651

15651번: N과 M (3)

 

 

 

기본 알고리즘

재귀함수를 이용해 구현한 중복순열

 

 

 

전체 코드

 

방법1 - 순열 코드에서 bool selected[] 코드 부분 제거

순열 코드 참고(scarlettb.tistory.com/126)

//백준15651 N과M(3)                                                            
#include <iostream>
#include <vector>
using namespace std;
 
const int MAX = 7;
int N, M;
int arr[MAX];
vector<int> v;
 
void print() {
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << "\n";
}
 
void DFS(int cnt) {
    if (cnt == M) {
        print();
        return;
    }
    for (int i = 0; i < N; i++) {
        v.push_back(arr[i]);
        DFS(cnt + 1);
        v.pop_back();
    }
}
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        arr[i] = i + 1; //arr[0]=1, arr[1]=2, ...
    }
 
    DFS(0);
 
    return 0;
}

 

 

 

방법2 - int selected[] 사용

selected[cnt] = arr[i]  //cnt번째 뽑은 카드는 arr[i]

//백준15651 N과M(3)                                                            
#include <iostream>
using namespace std;
 
const int MAX = 7;
int N, M;
int arr[MAX];
int selected[MAX];
 
void print() {
    for (int i = 0; i < M; i++) {
        cout << selected[i] << " ";
    }
    cout << "\n";
}
 
void DFS(int cnt) {
    if (cnt == M) {
        print();
        return;
    }
    for (int i = 0; i < N; i++) {
        selected[cnt] = arr[i];
        DFS(cnt + 1);
    }
}
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        arr[i] = i + 1; //arr[0]=1, arr[1]=2, ...
    }
 
    DFS(0);
 
    return 0;
}