백준 15649번(완전 탐색)

백준 15649번(완전 탐색)

이 문제는 처음에는 next_permutation을 중첩해서 사용하여 풀었었지만 시간초과가 발생하였습니다. 이 문제는 주어지는 N, M의 값이 작기에 재귀함수로 해결할 수 있었습니다. 1~N을 1부터 하나씩 선택하고 checked로 선택됬는지를 구분해주며 오름차순으로 차례로 재선택해줍니다. 이 문제를 풀면서 가장 놀라웠던 것은 endl을 사용했을 경우 시간초과로 문제를 해결할 수 없었다는 것입니다. 개인적으로는 endl을 사용시 "\
n"으로 해석하는 과정이 필요해서 시간초과가 나는 것으로 추측하고 있습니다.

#include <iostream>

using namespace std;

int N;
int M;
int arr[9];
bool checked[9];

void func(int count) {
	if (M == count) {
		for (int i = 0; i < M; i++) {
			cout << arr[i] << " ";
		}
		puts("");
		return;
	}
	for (int i = 1; i <= N; i++) {
		if (!checked[i]) {
			checked[i] = true;
			arr[count] = i;
			func(count + 1);
			checked[i] = false;
		}
	}
}

int main() {
	cin >> N;
	cin >> M;

	func(0);

	return 0;
}