백준 15655번: N과 M (6) (C++)

문제 링크는 다음과 같다.

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

15655번: N과 M (6)

 

수열에 오름차순이라는 조건이 존재하기 때문에 수열을 만들기 전에 입력받은 수들을 오름차순 정렬해준다.

 

또한 증가수열로 나타내야 하기 때문에 특정 자리의 숫자로는, 이 전 자리의 숫자보다 큰 숫자만 올 수 있다.

 

즉 길이 3인 수열을 만들어야 하는데, 첫 번째 숫자를 3으로 정해놨다고 하자.

 

3 _ _

 

이런 상태인데, 2번째 자리에 올 수 있는 숫자는 3보다 큰 숫자라는 뜻이다.

 

따라서 arr[k - 1] < num[i] 이 조건을 추가해서 구현해주면 된다.

 

물론 다음 재귀로 들어가기 전에 전역변수를 둬서 i를 저장해두거나, 재귀 함수의 인자로 몇 번째 index의 숫자를 사용했는지 관리해주는 방법도 있다.

 

func(1)은 이제 첫번째 자리의 숫자를 정해야 한다는 의미이다.

 

따라서 base condition은 이제 M+1번째 자리의 숫자를 정할 타이밍 일 것이다. 이때가 M번째 숫자까지 결정되었다는 의미이기 때문이다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int N, M, num[10], arr[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] && num[i] > arr[k - 1]) {
			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;
}