[BOJ] 15649_N과 M(1) with cpp

# 생각

조합의 개수를 구하는 문제이다

다중 for문을 사용하지 않고 backtracking 방법을 사용하면 된다

 

각 숫자는 수열에서 딱 한번씩만 사용되므로

bfs / dfs에서의 풀이를 활용하여 각 수에 대한 bool형 배열 bUsed를 선언,

해당 수를 사용 유무를 저장한다

 

1부터 n까지 수에 대해 사용되지 않은 수가 있다면 그 수를 넣고

사용했다고 true로 명시한 후에 다음 수를 정하는 함수를 재귀방식으로 작성한다

수를 정한 모든 경우에 대해 다 확인한 후 다시 false로 되돌아가주면

원하는 수열을 뽑아낼 수 있다

 

 

# 전체 코드

#include <bits/stdc++.h>
using namespace std;
// R : 1s, 512MB
// 1 <= M <= N <= 8
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] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 1; i <= n; i++)	// 1부터 n까지의 수에대해
	{
		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을 이용한 코드

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

void dfs2(int n, int m)
{
	vector<int> v;
	for (int i = 1; i <= n; i++)
	{
		v.push_back(i);
	}
	do
	{
		reverse(v.begin() + m, v.end());
		for (int i = 0; i < m; i++)
		{
			cout << v[i] << ' ';
		}
		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/15649

15649번: N과 M (1)