[15652] N과 M(4) - 중복 조합 ★★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

---

[ 문제 접근 ]

 

(3) 중복 순열에 이어서 이번 문제는 중복 조합 문제.

 

2 가지 방법으로 풀어보았다.

 

---

[ 풀이 1 ]

 

#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
 
using std::cin; using std::cout;
using std::vector;

int n, m;
int arr[9];
vector<int> buffer;

void repeat_combination(int k, int idx,int r) {
	if (r == 0) {
		for (auto elem : buffer)cout << elem << " ";
		cout << '\n';
		return;
	}

	for (int i = idx; i < n; i++) {
		buffer[k] = arr[i];
		repeat_combination(k + 1, i,r-1);
	}

}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		arr[i] = i + 1;
	}
	buffer.resize(m);
	repeat_combination(0,0,m);


	return 0;
}

 

[ 풀이 2 ]

 

#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
 
using std::cin; using std::cout;
using std::vector;

int n, m;
int arr[9];
vector<int> buffer;

void repeat_combination(int k, int idx,int r) {
	
	if (r==0) {
		for (auto elem : buffer)cout << elem << " ";
		cout << '\n';
		return;
	}
	else if (k==n) {
		return;
	}

	buffer[idx] = arr[k];
	repeat_combination(k, idx + 1, r - 1);

	repeat_combination(k+1, idx, r);

}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		arr[i] = i + 1;
	}
	buffer.resize(m);
	repeat_combination(0,0,m);


	return 0;
}

---

[ Key Point ]

 

👉 첫번째 방법은 다음 buffer[ ] 에 넣어질 원소는 자기 자신 이상만 가능하기에 i = idx 부터 시작.

 

👉 두번째 방법은 arr[k] 와 arr[k]를 선택하지 않았을때로 나눠서 recursive 하게 구현하였는데,

조합을 구현한 방법과 상당히 유사하다. 하지만 조합은 arr[k]를 선택했을때 다음 재귀함수에 k+1의 인자로 전달하지만

중복 조합은 다음 원소가 중복 될 수도 있으므로 k를 인자로 넘겨준다.

 

---

[ 다른 사람 풀이 ]

 

ref :: https://tooo1.tistory.com/315