[BOJ] 15650_N과 M(2) with cpp

# 생각

출력 결과를 보면 한번 선택한 수는 여러번 사용이 불가하므로 잘 걸러내주자

 

또한 고른 수열은 오름차순이어야 하기 때문에

시작지점을 잘 설정해 주어야 한다

int cnt = arr[k - 1] + 1;

 

 

# 전체 코드

// 1s, 512MB
// 1 <= M <= 8
#include <bits/stdc++.h>
using namespace std;

int arr[10];
bool bUsed[10];

void funcRecursive(int k, int n, int m)	// 현재 k까지 수를 선택했다
{
	if (k == m)	// m개를 모두 택했으면
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << ' ';	// arr에 기록해둔 수를 출력
		}
		cout << '\n';
		return;
	}
	int cnt = arr[k - 1] + 1;
	//int cnt = 1;	// 시작지점, k = 0일 때는 1
	//if(cnt != 0) cnt = arr[k - 1] + 1;	// k != 0일 경우 arr[k-1] + 1
	for (int i = cnt; i <= n; i++)
	{
		if (bUsed[i] == false)	// 아직 i가 사용되지 않았으면
		{
			arr[k] = i;	// k번째 수를 i로 정한다
			bUsed[i] = true;	// i를 사용
			funcRecursive(k + 1, n, m);	// 다음 수를 정하러 한 단계 더
			bUsed[i] = false;	// k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 미사용
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N, M;
	cin >> N >> M;
	funcRecursive(0, N, M);
}

 

 

# next_permutation을 이용한 코드

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

void dfs2(int n, int m)
{
	vector<int> v;
	for (int i = 0; i < n; i++)
	{
		v.push_back(i < m ? 0 : 1);
	}
	do
	{
		for (int i = 0; i < n; i++)
		{
			if (v[i] == 0)
			{
				cout << i + 1 << ' ';
			}
		}
		cout << '\n';
	} while (next_permutation(v.begin(), v.end()));
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N, M;
	cin >> N >> M;
	dfs2(N, M);
}

---

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

15650번: N과 M (2)