중복 조합(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)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
구현
조합 구현에서 자신을 선택하고 이후 재귀에서 자신의 위치를 넘김. ( 자신을 다시 선택하거나, 내 다음 원소를 선택하거나 )
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#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;
}
|
cs |
그렇다면 중복을 허용하지만 최대 중복 개수가 존재하면 어떻게 하면 될까?
-> 선택할 때마다 count를 감소시켜 주고 count가 0이면 스킵한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#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;
}
|
cs |
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