[백준 15657번] N과 M(9) C++ 풀이

시간 제한

1초

메모리 제한

512MB

문제

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

입력

첫째 줄에 N과 M이 주어진다.(1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

내 맞은 풀이

#include<bits/stdc++.h>
using namespace std;

int n(0), m(0);
int inputSeq[10] = { 0 };
bool isUsed[10] = { 0 };
int outputSeq[10] = { 0 };

void makeSeq(int cur) {
	if (cur == m) {
		for (int i = 0; i < m; i++) {
			cout << outputSeq[i] << ' ';
		}
		cout << '\n';
		return;
	}
	int before = -1;
	for (int i = 0; i < n; i++) {
		if (!isUsed[i] && before != inputSeq[i]) {
			isUsed[i] = true;
			outputSeq[cur] = inputSeq[i];
			before = inputSeq[i];
			makeSeq(cur + 1);
			isUsed[i] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> inputSeq[i];
	}
	sort(inputSeq, inputSeq + n);
	makeSeq(0);
	return 0;
}

백트래킹을 이용한다.
isUsed로 inputSeq에서 이미 사용한 숫자인지 체크하는 한편 직전에 사용했던 숫자와 일치하는지도 확인한다.
isUsed는 inputSeq를 인덱스대로 차례로 훑으므로 만약 중복된 숫자가 input에 있으면 이를 걸러낼 수 없다.
따라서 숫자를 정할 때마다 before에 그 수를 저장해서 다음 함수에 인자로 넘겨서 다음에 숫자를 정할 때 중복되는 수를 사용하지 않도록 한다.