[백준] 15651 N과 M (3) - 중복순열

15650 N과 M (2)를 풀었다면 정말 쉽게 풀리는 문제이다.

#include <cstdio>
int N, M;
char a[15];

void repeated_permutation(int depth){
    if (depth == M){
        for (int i=0; i<2 * M; ++i) printf("%c", a[i]);
        printf("\n");
        return;
    }
    
    for (int i=1; i<=N; ++i){
        a[depth * 2] = i + '0';
        repeated_permutation(depth + 1);
    }
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i=0; i<2 * M; ++i) a[i] = ' ';
    repeated_permutation(0);
    return 0;
}

재귀 함수를 호출할 수록 depth는 깊어진다. depth는 몇번째 수까지 순열을 만들었는지를 의미하기도 한다.

depth를 고정시킨 채로, 수를 바꾸어 가며 중복 순열의 수를 만든다.

 

아랫 것은 stack을 이용한 버전이다.

#include <cstdio>
#include <vector>

using namespace std;
typedef vector<int> vi;
int N, M;

void printlnVector(vi & v){
    for (int i=0; i<v.size(); ++i) printf("%d ", v[i]);
    printf("\n");
}

void repeated_permutation(vi & v){
    if (v.size() == M){
        printlnVector(v);
        return;
    }
    
    for (int i=1; i<=N; ++i){
        v.emplace_back(i);
        repeated_permutation(v);
        v.pop_back();
    }
}

int main() {
    scanf("%d %d", &N, &M);
    vi vec;
    repeated_permutation(vec);
    return 0;
}