백준 15654: N과 M (5)

문제 요약

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열

문제 분류

• 백트래킹

문제 풀이

이전 포스팅 [C++] 백준 15649: N과 M (1)을 참고하여 코드를 수정하였다.

이번에는 출력이 i가 아닌 입력으로 주어지므로, 입력을 배열로 저장해야한다.

vector를 이용하여 입력받고, sort()를 이용하여 정렬한다.

나머지 코드는 N과 M(1)과 거의 동일하다.

방문하지 않았다면 ary에 넣어주고, visited를 true로 바꾼 다음, 다음 탐색을 진행한다. 다음 탐색이 끝났다면 visited를 다시 false로 바꿔준다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> v;
int res[8], n, m;
bool visited[8];

void dfs(int cnt)
{
	if (cnt >= m) {
		for (int i = 0; i < m; i++)
			printf("%d ", res[i]);
		printf("\n");
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			res[cnt] = v[i];
			visited[i] = true;
			dfs(cnt + 1);
			visited[i] = false;
		}
	}
}

int main()
{
	int input;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		scanf("%d", &input);
		v.push_back(input);
	}
	sort(v.begin(), v.end());
	dfs(0);
}