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

문제

[C++] 백준 15654: N과 M (5) SILVER 3
https://www.acmicpc.net/problem/15654

 

---

 

접근 방법

이 문제(백준 15654)는 주어진 N개의 서로 다른 자연수 중에서 M개를 골라 나열하는 모든 수열을 출력하는 문제다.
즉, 중복 없는 순열을 구하는 문제이고, 입력으로 주어진 수들을 사용한다는 점이 15649랑 다르다.

 

문제 조건:

• 수들은 1, 2, 3, … 이 아니라 입력으로 주어지는 임의의 수들
• 한 수는 한 번만 사용할 수 있음 (중복 선택 불가)
• 출력은 사전 순(오름차순) 으로 나와야 함

그래서 풀이 전략은:

1. 먼저 입력받은 수들을 vect에 저장하고 sort로 정렬한다.
   → 이렇게 하면 백트래킹을 할 때 작은 수부터 탐색하게 되어, 자연스럽게 사전 순으로 수열이 출력된다.
2. picked 벡터에는 현재까지 선택한 수열을 저장한다.
3. visited[i] 배열을 이용해서 vect[i]를 이미 사용했는지 여부를 체크해 중복 사용을 막는다.
4. 깊이가 m에 도달하면(depth == m), picked를 그대로 출력한다.

 

참고하면 좋은 포스팅:

https://xeungcoding.tistory.com/89

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

 

구현 시 주의할 점

 

• 입력 수 자체를 사용해야 하므로 1, 2, 3, … 를 돌리는 게 아니라 vect[i]를 사용하는 점이 중요하다.
• 15650은 조합이라 start로 범위를 제한하고,
  15654는 순열이라 visited로 중복 사용을 막는다.

 

 

---

 

코드

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

int n, m;
vector<int> vect;
vector<int> picked;
vector<bool> visited;

void backTracking(int depth)
{
	if (depth == m)
	{
		for (int i = 0; i < m; i++)
			cout << picked[i] << ' ';
		cout << '\n';

		return;
	}
	for (int i = 0; i < n; i++)
	{
		if (visited[i] == true) continue;

		picked.push_back(vect[i]);
		visited[i] = true;

		backTracking(depth + 1);

		picked.pop_back();
		visited[i] = false;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	vect.resize(n, 0);
	visited.resize(n, false);
	for (int i = 0; i < n; i++)
		cin >> vect[i];

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

	backTracking(0);

	return 0;
}