[C++]N과 M (5 ~ 8) - BOJ 15654 ~ 15657

이 게시물에는 N과 M 시리즈 5부터 8번까지 4문제의 풀이가 들어있음.
BOJ 15654 15655 15656 15657

---

모든 조건부 조합의 경우를 출력해야 하는 완전탐색 문제다.
사전순 출력이므로 dfs로 쉽게 풀 수 있다.
또 cout << endl; 는 느리게 작동하므로 cout << "\n"; 를 사용해야 한다.

앞선 1 ~ 4번 문제들과 다르게 주어진 수 들로 수열을 만들어야 한다.
또 숫자를 입력받고 오름차순 정렬해야 사전순 출력이 쉽다.
그 부분을 제외하고 방식은 동일하다.

---

BOJ 15654 - N과 M (5)

chk[]를 사용해 dfs수행 도중 같은 레벨의 depth에서 동일한 수를 사용하지 않도록 한다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, arr[10], chk[10], seq[10];
void dfs(int c) {
	if(c == m) {
		for(int i = 0; i < m; i++) cout << arr[i] << " ";
		cout << "\n";
		return;
	}
	for(int i = 1; i <= n; i++)
		if(!chk[i]) {
			arr[c] = seq[i];
			chk[i] = 1;
			dfs(c + 1);
			chk[i] = 0;
		}
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> seq[i];
	sort(seq, seq + n + 1);
	dfs(0);
}

BOJ 15655 - N과 M (6)

5번 문제와 다르게 오름차순이라는 조건이 생겼으므로 이전 depth에 담긴 값보다 클 경우에만 수를 넣도록 한다.
이 조건이 5번 문제의 chk[] 역할을 내포하고 있으므로 chk[]는 필요없다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, arr[10], seq[10];
void dfs(int c) {
	if(c == m) {
		for(int i = 0; i < m; i++) cout << arr[i] << " ";
		cout << "\n";
		return;
	}
	for(int i = 1; i <= n; i++)
		if(arr[c - 1] < seq[i]) {
			arr[c] = seq[i];
			dfs(c + 1);
		}
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> seq[i];
	sort(seq, seq + n + 1);
	dfs(0);
}

BOJ 15656 - N과 M (7)

같은 수를 여러 번 골라도 되므로 조건없는 완전탐색이다.
위의 문제들에서 조건을 삭제하면 된다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, arr[10], seq[10];
void dfs(int c) {
	if(c == m) {
		for(int i = 0; i < m; i++) cout << arr[i] << " ";
		cout << "\n";
		return;
	}
	for(int i = 1; i <= n; i++) {
		arr[c] = seq[i];
		dfs(c + 1);
	}
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> seq[i];
	sort(seq, seq + n + 1);
	dfs(0);
}

BOJ 15657 - N과 M (8)

말만 복잡하지 요약하자면 6번 문제에서 중복을 허용하는 오름차순일 뿐이다.
< 를 <= 로 바꿔주면 된다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, arr[10], seq[10];
void dfs(int c) {
	if(c == m) {
		for(int i = 0; i < m; i++) cout << arr[i] << " ";
		cout << "\n";
		return;
	}
	for(int i = 1; i <= n; i++)
		if(arr[c - 1] <= seq[i]) {
			arr[c] = seq[i];
			dfs(c + 1);
		}
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> seq[i];
	sort(seq, seq + n + 1);
	dfs(0);
}