[C++]N과 M (9 ~ 12) - BOJ 15663 ~ 15666

이 게시물에는 N과 M 시리즈 9부터 12번까지 4문제의 풀이가 들어있음.
BOJ 15663 15664 15665 15666

---

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

앞선 5 ~ 8번 문제들과 다르게 주어지는 수 중에 중복되는 숫자가 존재한다.

중복된 수열을 출력하면 안되므로 같은 레벨의 depth에서 같은 수를 중복해서 호출하지 않도록 해야 한다.
따라서 tmp에 해당 값을 담고 매번 체크하며 넘어간다.
여기서 tmp는 지역변수로 정의해야한다.
각 depth의 tmp는 dfs가 호출 될 때 마다 의미하는 바가 다르기 때문이다.

---

BOJ 15663 - N과 M (9)

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;
	}
	int tmp = 0;
	for(int i = 1; i <= n; i++)
		if(!chk[i] && tmp != seq[i]) {
			tmp = 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 15664 - N과 M (10)

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

#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;
	}
	int tmp = 0;
	for(int i = 1; i <= n; i++)
		if(!chk[i] && tmp != seq[i] && arr[c - 1] <= seq[i]) {
			tmp = 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 15665 - N과 M (11)

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

#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;
	}
	int tmp = 0;
	for(int i = 1; i <= n; i++)
		if(tmp != seq[i]) {
			tmp = 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 15666 - N과 M (12)

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

#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;
	}
	int tmp = 0;
	for(int i = 1; i <= n; i++)
		if(tmp != seq[i] && arr[c - 1] <= seq[i]) {
			tmp = 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);
}