[백준 C++] 15652번 : N과 M(5)

1. 문제

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

15654번: N과 M (5)

2. 알고리즘 분류

• 백트래킹

 

3. 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
int visited[10];	// 사용된 숫자 체크(중복 방지용)
vector<int> inputs;
vector<int> nums;

// 수열을 구하는 함수
// lv : 뽑은 숫자의 갯수
void permutation(int lv) {

	// M개의 숫자를 뽑았을 경우, 출력
	if (lv == M) {
		for (int i = 0; i < nums.size(); i++) {
			cout << nums[i] << " ";
		}
		cout << '\n';

		return;
	}

	
	for (int i = 0; i < N; i++) {

		// 해당 숫자가 사용되었으면 skip
		if (visited[i]) continue;

		visited[i] = 1;		// 숫자 사용 체크
		nums.push_back(inputs[i]);	// 해당 숫자 뽑기
		permutation(lv + 1);
		nums.pop_back();		// 해당 숫자 뽑기
		visited[i] = 0;		// 숫자 사용 체크 해제
	}
}

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

	cin >> N >> M;

	// 해당 수열을 inputs에 저장
	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;
		inputs.push_back(n);
	}

	// 사전 순으로 증가하는 순서로 출력하기 위해 사전 순으로 정렬
	sort(inputs.begin(), inputs.end());

	// 수열 구하기
	permutation(0);

	return 0;
}

 

4.  상세 설명

1. 해당 수열에서 특정 수 뽑기
2. 특정 수를 뽑을 때, 사용 여부(visited)를 확인하고 체크 되어있으면 건너뛰기
3. 특정 수를 뽑고 나서, 사용 여부(visited)를 체크
4. 뽑은 수가 M개라면, 뽑는 것을 중단하고 뽑은 수들을 출력
5. 이전에 뽑은 수를 하나하나씩 되돌리고, 1 ~ 3번을 반복

 

5.  문법

5 - 1) 사전 순으로 정렬(오름차순)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	vector<int> inputs;
    
    inputs.push_back(4);
    inputs.push_back(2);
    inputs.push_back(6);
    
    sort(inputs.begin(), inputs.end());
    
    return 0;
}

 

5 - 2) 주어진 수열에서 M개를 고른 부분 수열(중복 수열 X,  사전 순)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
int visited[10];
vector<int> inputs;
vector<int> nums;

void permutation(int lv) {
	if (lv == M) {
		for (int i = 0; i < nums.size(); i++) {
			cout << nums[i] << " ";
		}
		cout << '\n';

		return;
	}

	for (int i = 0; i < N; i++) {

		if (visited[i]) continue;

		visited[i] = 1;
		nums.push_back(inputs[i]);
		permutation(lv + 1);
		nums.pop_back();
		visited[i] = 0;
	}
}

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

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;
		inputs.push_back(n);
	}

	sort(inputs.begin(), inputs.end());

	permutation(0);

	return 0;
}