백준 15652번: N과 M (5) (C++)

문제 링크

https://www.acmicpc.net/problem/15654

15654번: N과 M (5)

 

사용할 수 있는 수들을 입력으로 받는다.

 

수열들을 오름차순으로 뽑아내야 한다.

 

사용되는 숫자들을 사전에 오름차순으로 정렬해두면 된다.

 

 

재귀함수의 인자는 숫자의 번호라고 생각하면 되겠다. 즉 k가 1인경우는, 첫번째 숫자를 결정할 차례라는 뜻이다.

 

길이를 M으로 입력받기 때문에, k가 M+1이 되면 M+1번째 숫자를 결정할 차례라는 의미이므로 이미 M번째 까지는 결정이 되었다는 의미이다.

 

따라서 k == M+1인 경우를 base condition으로 설정해주면 된다.

 

또한 재귀를 빠져나온 이후에는, 숫자를 사용중이 아닌 것이 되기때문에, isused값을 다시 false로 바꿔줘야한다.

 

만약 k를 전역변수로 두고 코딩을 한다면 k또한 재귀를 들어가기전에는 증가, 재귀에서 빠져 나온 이후에는 감소를 해줘야 할 것이다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int N, M;
int arr[10], num[10];
bool isused[10];

void func(int k) {
	if (k == M + 1) {
		for (int i = 1; i <= M; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}
	
	for (int i = 1; i <= N; i++) {
		if (!isused[i]) {
			arr[k] = num[i];
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}

}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> num[i];
	}
	sort(num + 1, num + N + 1);

	func(1);

	return 0;
}