백준 15649번: N과 M (1) (C++)

문제 링크는 다음과 같다.

 

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

15649번: N과 M (1)

 

문제 설명

 

1부터 N까지 자연수를 사용해서 길이 M의 수열을 만들면 된다.

 

숫자는 중복해서 사용할 수 없다. 그리고 수열의 출력은 오름차순으로 이루어져야한다.

 

중복이 없다는 조건을 만족시키기 위해서 특정 숫자가 사용되었는지 관리하기 위해서 isused 배열을 사용한다.

 

그리고 수열이 되는 숫자는 arr 배열에 저장된다.

 

재귀함수로 구현을 할 것이고, base condition은 수열의 길이 k = M이 되는 경우이다.

 

이때 수열이 완성되었으므로 출력을 해준다.

 

재귀함수를 빠져나온 이후에는 그 숫자가 사용중인 것이 아니게 되기 때문에 isused를 다시 false로 만들어주는 것이 중요하다.

 

arr값은 어짜피 이어서 덮어씌워질것이기때문에 고려하지 않아도 된다.

 

이 문제는 next_permutation을 활용해서도 구현이 가능할 것이다.

 

#include<iostream>
using namespace std;
int N, M;
void func(int* arr, bool* isused, int k) {
	if (k == M) {
		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 + 1] = i;
			isused[i] = true;
			func(arr, isused, k + 1);
			isused[i] = false;
		}
	}
}

int main(void) {
	int arr[10];
	bool isused[10];
	for (int i = 1; i <= 9; i++) {
		arr[i] = 0;
		isused[i] = false;
	}

	int k = 0;

	cin >> N >> M;
	
	func(arr, isused, k);

	return 0;
}