[C++]N과 M (1 ~ 4) - BOJ 15649 ~ 15652

이 게시물에는 N과 M 시리즈 1부터 4번까지 4문제의 풀이가 들어있음.
BOJ 15649 15650 15651 15652

---

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

---

BOJ 15649 - N과 M (1)

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

#include <iostream>
using namespace std;
int n, m, arr[10], chk[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] = i;
			chk[i] = 1;
			dfs(c + 1);
			chk[i] = 0;
		}
}
int main() {
	cin >> n >> m;
	dfs(0);
}

BOJ 15650 - N과 M (2)

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

#include <iostream>
using namespace std;
int n, m, arr[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] < i) {
			arr[c] = i;
			dfs(c + 1);
		}
}
int main() {
	cin >> n >> m;
	dfs(0);
}

BOJ 15651 - N과 M (3)

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

#include <iostream>
using namespace std;
int n, m, arr[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] = i;
		dfs(c + 1);
	}
}
int main() {
	cin >> n >> m;
	dfs(0);
}

BOJ 15652 - N과 M (4)

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

#include <iostream>
using namespace std;
int n, m, arr[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] <= i) {
			arr[c] = i;
			dfs(c + 1);
		}
}
int main() {
	cin >> n >> m;
	dfs(0);
}