[백준] 15666-N과 M (12)(C++)

문제링크:https://www.acmicpc.net/problem/15666

15666번: N과 M (12)

 

dfs연습문제입니다. 

• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다

두가지 조건을 만족시켜야 합니다. 

중복 수를 제거하고 sort 함수를 통해 오름차순 배열로 정렬시켰습니다.

그 이후 재귀식을 통해서 count값을 올리며 진행했습니다. 

void dfs(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < cnt; i++)
			cout << result[i] << ' ';
		cout << endl;
		return;
	}

	for (int i = 0; i < arr_index; i++) {
		bool jud = true;

		for (int j = 0; j < cnt; j++)
			if (result[j] > arr[i]) {
				jud = false;
				break;
			}


		if (jud == true)
		{
			result [cnt] = arr[i];
			dfs(cnt + 1);
		}
	}
}

위 처럼 구현하였습니다.

 

정답코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int n = 0, m = 0,arr_index=0,num;
int arr[8] = { 0 };
int result[8];
bool visited[8] = { 0 };
void dfs(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < cnt; i++)
			cout << result[i] << ' ';
		cout << endl;
		return;
	}

	for (int i = 0; i < arr_index; i++) {
		bool jud = true;

		for (int j = 0; j < cnt; j++)
			if (result[j] > arr[i]) {
				jud = false;
				break;
			}


		if (jud == true)
		{
			result [cnt] = arr[i];
			dfs(cnt + 1);
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		bool jud = true;
		cin >> num;
		for (int j = 0; j < arr_index; j++) {
			if (arr[j] == num) {
				jud = false;
				break;
			}
		}
		if (jud == true)
			arr[arr_index++] = num;
	}
	sort(arr, arr + arr_index);
	
	dfs(0);
}