C++ 백준 15654번

브루트 포스 문제 중에 재귀를 이용하는 친구이다!!

다른 N과 M문제는 정답률이 너무 높아서 올리기 머쓱하다!!!

백준 15654번 www.acmicpc.net/problem/15654

15654번: N과 M (5)

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

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

첫째줄에 N과 M이 주어지고 둘째 줄에 N개의 수가 주어진다. 이 N개의 수중에 M개를 골라 사전 순으로 가능한 모든 경우를 출력하는 문제이다.

입력을 받는 배열과 정답을 저장하는 배열, 수가 중복이 되면 안 되니까 그 수가 쓰였는지 안 쓰였는지를 저장하는 bool 배열을 만들고 입력 배열을 sort함수를 이용하여 오름차순으로 정렬하고 수열을 구하면 된다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int a[9];
int c[9]; // 정답 수열
bool b[9]; // b[i] == true 이면 a[i]가 이미 사용됐음
void go(int index, int n, int m) {
	if (index == m) {
		for (int i = 0; i < m; i++) {
			cout << c[i];
			if (i != m - 1) cout << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = 0; i < n; i++) {
		if (b[i]) continue; // a[i]가 사용됐으면 넘어감
		c[index] = a[i];
		b[i] = true;
		go(index + 1, n, m);
		b[i] = false;
	}
}
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	go(0, n, m);
}