중복 조합(combinations with repetition) / N과 M(4)

- 중복 조합

중복을 허용하여 원소를 선택하는 조합. n개의 원소를 r번 중복 허용하여 선택하는 경우의 수. nHr  = n+r-1Cr

 

예를 들어보자.

n개의 원소 {1,2,3,4,5}가 있다고 가정. 이때 3개를 중복 허용하여 선택한다고 하자.

{1,1,1} , {1,1,2}, {1,1,3}, ... , {1,2,2} , {1,2,3} , ... , {5,5,5} 가 될 것이다.

조합이므로 순서 개념이 없으므로 {1,1,2}, {1,2,1}, {2,1,1} 은 하나의 경우로 취급.  ( {1} 2개 , {2} 1개)

 

 

- 왜 nHr = n+r-1Cr 일까?

 

위의 예를 든 5H3을 생각해보자.

 

ㅁ ㅁ ㅁ 3개의 빈칸(r)과  / / / /  4개의 칸막이(n-1)가 있다고 생각.

 

ㅁ ㅁ ㅁ / / / /  -> 1 1 1 

ㅁ ㅁ / ㅁ / / /  -> 1 1 2

ㅁ ㅁ / / ㅁ / /  -> 1 1 3 

ㅁ / ㅁ ㅁ / / /  -> 1 2 2

/ / / / ㅁ ㅁ ㅁ  -> 5 5 5

 

 

빈칸 ㅁ 과 칸막이 / 를 배치하는 문제로 바꿔서 생각할 수 있다. 단 빈칸끼리와 칸막이끼리의 순서는 고려하지 않음.

총 7자리에서 빈칸 위치 3자리를 고르는 문제가 되기 때문에 7C3

 

일반화하면 전체 자리 수에서 빈칸 자리 r개를 뽑는 경우의 수 ( 빈칸 자리를 고르면 칸막이 자리가 정해짐 )

n+r-1Cr  = nHr 

 

 

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

구현

조합 구현에서 자신을 선택하고 이후 재귀에서 자신의 위치를 넘김. ( 자신을 다시 선택하거나, 내 다음 원소를 선택하거나 )

 

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<unordered_map>
#include<map>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#define INF 1e9
using namespace std;
using lld = long long int;
using pii = pair<int, int>;
 
bool visited[10];
int a[10];
int n, m;
 
void solve(int dep, int idx) {
    if(dep == m) {
        
        for(int i=0; i<m; i++) {
            cout << a[i] << " ";
        }
        cout << "\n";
        
        return;
    }
    
    for(int i=idx; i<=n; i++) {
        a[dep] = i;
        
        solve(dep+1, i);
    }
    
    return;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    
    solve(0, 1);
    
    return 0;
}
 
 
 

 

 

그렇다면 중복을 허용하지만 최대 중복 개수가 존재하면 어떻게 하면 될까?

-> 선택할 때마다 count를 감소시켜 주고 count가 0이면 스킵한다.

 

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<unordered_map>
#include<map>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#define INF 1e9
using namespace std;
using lld = long long int;
using pii = pair<int, int>;
 
bool visited[10];
int a[10];
int b[10];
int n, m;
 
void solve(int dep, int idx) {
    if(dep == m) {
        
        for(int i=0; i<m; i++) {
            cout << a[i] << " ";
        }
        cout << "\n";
        
        return;
    }
    
    for(int i=idx; i<=n; i++) {
        // 중복 허용 개수를 다 사용했으면 스킵.
        if(b[i] == 0) continue;
        
        a[dep] = i;
        
        b[i]--;
        solve(dep+1, i);
        b[i]++;
    }
    
    return;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    
    // 각 원소의 최대 중복 허용 개수
    for(int i=0;i<n;i++) {
        cin >> b[i];
    }
    
    solve(0, 1);
    
    return 0;
}
 
 
 

 

input

5 3
2 2 2 2 2  <- 원소별 중복 최대 허용 개수 

output

1 1 2 
1 1 3 
1 1 4 
1 2 2 
1 2 3 
1 2 4 
1 3 3 
1 3 4 
1 4 4 
2 2 3 
2 2 4 
2 3 3 
2 3 4 
2 4 4 
3 3 4 
3 4 4