백준 15655

코드 1)

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

int N, M;
bool state[10000]; // N개의 숫자에 대한 사용여부 상태
int arr[10000];  // 상태에 대한 데이터 배열이 {1,2,3} 순으로 정렬되어 있으면 상태배열에 [0],[1],[2] 각각 매칭됨
int temp[8]; // 재귀함수를 돌면서 모든 경우의 수를 체크해 출력하기 위한 용도

void func(int k) {

	if (k == M) {
		for (int i = 0; i < M; i++)
			cout << temp[i] << ' ';
		cout << '\n';
		return;
	}

	// 이전 인덱스 값보다 가장 큰 값이 없는 경우 재귀함수 종료
	if (temp[k - 1] == arr[N - 1]) return;

	int j = 0;
	if (k != 0) {				
		for (int i = 0; i < N; i++) {
			if (arr[i] > temp[k - 1]) {
				j = i;
				break;
			}
		}		
	}
		
	for (int i = j; i < N; i++) {
		if (state[i] == 0) {
			temp[k] = arr[i];
			state[i] = 1;
			func(k + 1);
			state[i] = 0;
		}
	}	
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	// 1.입력	
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N); // 오름차순 정렬
	func(0);
	
	return 0;
}

 

 

코드 2)

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

int N, M;
bool state[8]; // N개의 숫자에 대한 사용여부 상태
int arr[8];  // 오름차순으로 temp에 해당되는 값이 위치하는 인덱스를 저장
int temp[8]; // N개의 값

void func(int k) {

	if (k == M) {
		for (int i = 0; i < M; i++)
			cout << temp[arr[i]] << ' ';
		cout << '\n';
		return;
	}

	int st = 0;
	if (k != 0) st = arr[k - 1] + 1;
	for (int i = st; i < N; i++) {
		if (state[i] == 0) {
			arr[k] = i;
			state[i] = 1;
			func(k + 1);
			state[i] = 0;
		}
	}	
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	// 1.입력	
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> temp[i];
	}
	sort(temp, temp + N); // 오름차순 정렬
	func(0);
	
	return 0;
}

오름차순으로 값이 저장되어있는 temp에 해당되는 값이 위치하는 인덱스를 오름차순으로 저장하는 arr 배열을 만듬

 

temp는 값이 오름차순으로 정렬되어 있는 배열일뿐고 실제로는 arr에서 temp에 있는 인덱스를 가져와서(이전의 인덱스보다 +1 더 큰것을 temp에서 가져오는데 temp가 오름차순으로 정렬이 되어있기 때문에 +1을 하면 인덱스에 해당되는 값은 무조건 이전 인덱스의 값보다 때문에)길이가 M인 수열을 오름차순으로 모두 구한다.