[BOJ - 15654] N과 M(5)

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

15654번: N과 M (5)

 

이전에 풀었던 N과 M(1)과 같은 문제입니다.

 

입력만 늘어났지 예시를 보시면 순열 문제라는 것을 금방 파악할 수 있습니다.

(잘 모르시겠다면 이전 게시물(N과 M(1)문제)을 참고해주세요)

 

풀이 과정은 다음과 같습니다.

 

1. 입력을 받고 vec이라는 벡터에도 입력값을 넣어줍니다.

 

2. vec을 정렬합니다.

 

3. dfs와 백트래킹으로 모든 순열을 구해줍니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;
int visited[9];
vector<int> vec, sel;

void dfs() {
	if (sel.size() == m) {

		for (int i = 0; i < sel.size(); i++) {
			printf("%d ", sel[i]);
		}
		printf("\n");

		return;
	}

	for (int i = 0; i < vec.size(); i++) {
		if (visited[i] == 0) {
			visited[i] = 1;
			sel.push_back(vec[i]);
			dfs();
			visited[i] = 0;
			sel.pop_back();
		}
	}
}

int main(void) {

	scanf("%d %d", &n, &m);

	for (int temp, i = 0; i < n; i++) {
		scanf("%d", &temp);
		vec.push_back(temp);
	}
	
	sort(vec.begin(), vec.end());

	dfs();

	getchar();
	getchar();

	return 0;
}