백준 15650번: N과 M (2) (C++)

문제 링크는 다음과 같다.

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

15650번: N과 M (2)

 

N과 M (1)과 약간의 차이가 있다.

 

수열 자체가 증가수열이면 된다.

 

이를 위해서는 기존에 재귀를 돌리던 루프의 시작 인덱스를 바로 직전 자리의 숫자 + 1로 해주면 된다.

 

직전 자리의 숫자는 어짜피 사용 중이기 때문에 그다음 숫자로 해주면 되는 것이다.

 

주의할 것은, 가장 처음 즉 이전 자리수가 존재하지 않는 경우인데, 그 경우에는 N의 시작 값인 1로 값을 정해주면 된다.

 

#include<iostream>
using namespace std;
int N, M;
void func(int* arr, bool* used, int k) {
	//base condition
	if (k == M) {
		for (int i = 1; i <= k; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}
	
	int init;
	if (k == 0) init = 1;
	else
		init = arr[k] + 1;

	for (int i = init; i <= N; i++) {
		if (!used[i]) {
			arr[k + 1] = i;
			used[i] = true;
			func(arr, used, k + 1);
			used[i] = false;
		}
	}
}
int main(void) {
	
	cin >> N >> M;
	
	int arr[10]; //길이 8이 최댄데 1 - indexed
	bool used[10]; // 1~9

	for (int i = 1; i <= 9; i++) {
		arr[i] = 0;
		used[i] = false;
	}
	
	func(arr, used, 0);// 0번째 자리까지 다 정해졌다. 이번에 1번째 자리 정할 차례다
	return 0;
}