[15650] N과 M (2)- 조합 ★★☆☆ / 복습 ○

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

15650번: N과 M (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];
bool include[9];
	
void combination(int k,int r) {
	if (r==0) {
		for (int i = 0; i < n; i++) {
			if (include[i]) cout << arr[i] << " ";
		}
		cout << '\n';
		return;
	}
	else if (k == n) {
		return;
	}

	include[k] = true;
	combination(k + 1, r - 1);

	include[k] = false;
	combination(k + 1, 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;
	}
	combination(0,m);
	
	return 0;
}

 

include 배열 만들어서 (  뽑을때 + 안뽑았을때 ) 를 재귀적으로 탐색.

 

조합을 푸는 여러가지 방법중에 가장 쉬운 방법이 아닌가 싶음.

---

[ 방법 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 combination(int k,int r,int idx) {
	if (r==0) {
		for (auto elem : buffer) cout << elem << " ";
		cout << '\n';
		return;
	}
	else if (k == n) return;

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

	combination(k+1,r,idx);
}


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);
	combination(0,m,0);
	
	return 0;
}

 

nCr = n-1Cr-1 + n-1Cr 을 이용한 풀이.

 

기억해야할 점은 idx (인덱스) 변수를 만들어줘야된다는 점이다.

---

[ 방법 3 ]

 

#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 combination(int k,int idx) {
	if (k == m) {
		for (auto elem : buffer) {
			cout << elem << " ";
		}
		cout << '\n';
		return;
	}
	for (int i=idx; i < n; i++) {
		buffer[k] = arr[i];
		combination(k + 1, i + 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);
	combination(0,0);
	
	return 0;
}

 

 

 

중복 순열 구하는 코드와 비슷한 코드.

다음에 올 수 있는 코드를 하나 씩 크게 하면서 재귀.

 

---

[ 방법 4 ]

 

STL 의 prev_permutation , next_permutation을 이용한 풀이

 

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

int n, m;
int arr[9];
vector<bool> temp;
	
void combination() {
	do {
		for (int i = 0; i < n; i++) {
			if (temp[i]) cout << arr[i] << " ";
		}
		cout << '\n';
	} while (std::prev_permutation(temp.begin(),temp.end()));
}

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;
	}
	temp.resize(n);

	for (int i = 0; i < m; i++) {
		temp[i] = true;
	}
	combination();

	return 0;
}

 

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

int n, m;
int arr[9];
vector<bool> temp;
	
void combination() {
	do {
		for (int i = 0; i < n; i++) {
			if (!temp[i]) cout << arr[i] << " ";
		}
		cout << '\n';

	} while (std::next_permutation(temp.begin(),temp.end()));
}

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;
	}
	temp.resize(n);
	for (int i = n-m; i < n; i++) {
		temp[i] = true;
	}
	combination();

	return 0;
}

---

[ 다른 사람 풀이 ]

 

ref :: https://m.blog.naver.com/ndb796/221240353788

ref ::