[백준] 15655번: N과 M

by

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

15655호: N과 M (6)

N개의 자연수와 자연수 M이 주어지면 다음 조건을 만족하는 길이 M의 모든 시퀀스를 찾는 프로그램을 작성하십시오. N개의 자연수는 모두 다른 수입니다. N개의 자연수에서 선택된 M개의 수열

'추천 관련글,

www.acmicpc.net

솔루션 프로세스 1

M개 요소를 선택하여 N개의 개수 아래 중복 없이 배열한 경우의 개수를 출력해야 한다. 숫자를 중복 없이 하나씩 삽입하여 시퀀스가 ​​완료되면 출력되고 이전 상태로 돌아갑니다. 이후 i번째 주소로 K번째 숫자가 설정되는 경우를 모두 확인하였으므로 다시 i를 사용하지 않은 것으로 처리하고 또 다른 시퀀스를 완성한다.

1. 현재 선택한 숫자의 수를 매개변수로 사용하는 재귀 함수를 선언합니다.

2. 현재 선택된 숫자의 개수가 M이 되면 시퀀스가 ​​완료되어 출력됩니다.

3. 현재 선택된 숫자의 개수가 1보다 크면(예: K==1), 입력된 숫자를 오름차순으로 시퀀스로 생성해야 하므로 정렬합니다.

4. 숫자 앞에 선택된 주소에 1을 더하여 얻은 값에서 선택을 시작합니다.

4. 1부터 N까지의 번호는 아직 선택되지 않은 주소를 k번째 번호로 설정하고 사용된 주소로 처리합니다.

5. 1단계에서 선언한 함수를 실행하여 2단계와 3단계를 재귀적으로 호출하는 k+1개의 숫자를 찾습니다.

6. 5단계가 완료되면 모든 케이스가 검토되었으므로 재사용하지 않는 번호로 처리됩니다.

소스 코드 1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define fastio() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

bool isused(10);
int arr(10);
int n, m;
vector<int>num_arr;
void bt(int k) //현재 선택한 수의 개수가 k개임
{
	if (k == m) //m개를 모두 택했으면
	{
		for (int i = 0; i < m; i++)
			cout << num_arr(arr(i)) << ' '; //arr에 기록해둔 주소에 해당하는 수를 출력
		cout << '\n';
		return;
	}
	int num = 0;
	if (k >= 1)
		num = arr(k - 1) + 1;

	for (int i = num; i < n; i++) //num부터 n까지의 주소에 대해
	{
		if (!isused(i)) //아직 i번째 주소가 선택되지 않았다면
		{
			arr(k) = i; //k번째 수를 i번째 주소로 정함
			isused(i) = 1; //i번째 주소를 사용처리
			bt(k + 1); //다음 자리 수를 구하러감.
			isused(i) = 0; //모든 경우에 대해 다 확인햇으니
						   //i번째 주소를 다시 사용되지 않았다고 처리함.
		}
	}
}

int main(void)
{
	fastio();

	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		int v;
		cin >> v;
		num_arr.push_back(v);
	}
	sort(num_arr.begin(), num_arr.end());
	bt(0);



}

솔루션 프로세스 2

next_permutation을 사용하여 시퀀스를 만들 수 있습니다.

1. 시퀀스를 생성하고 선택하려는 만큼 tmp에 0을 입력합니다.

2. 시퀀스를 오름차순으로 정렬합니다.

3. next_permutation에서 tmp의 오름차순으로 순열을 생성할 때 tmp가 0이면 해당 시퀀스의 값이 출력됩니다.

소스 코드 2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define fastio() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int n, m;



int main(void)
{
	fastio();

	cin >> n >> m;
	vector<int>num;
	vector<int>tmp;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		num.push_back(a);
		tmp.push_back(i < m ? 0 : 1); //m의 개수만큼 0을 넣어준다.
	}
	sort(num.begin(), num.end()); //수열 오름차순 정렬

	do {

		for (int i = 0; i < n; i++)
		{
			if (tmp(i) == 0)
				cout << num(i) << ' ';
		}
		cout << '\n';

	} while (next_permutation(tmp.begin(), tmp.end())); // 정해진 개수만큼 숫자 뽑기


}
/*

*/