[백준] 15654번 N과 M (5) C++ 풀이

---

알고리즘 분류

• 백트래킹

---

문제 설명

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열

---

입력 설명

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

---

출력 설명

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

예제 입력

3 1
4 5 2

4 2
9 8 7 1

4 4
1231 1232 1233 1234

---

예제 출력

2
4
5

1 7
1 8
1 9
7 1
7 8
7 9
8 1
8 7
8 9
9 1
9 7
9 8

1231 1232 1233 1234
1231 1232 1234 1233
1231 1233 1232 1234
1231 1233 1234 1232
1231 1234 1232 1233
1231 1234 1233 1232
1232 1231 1233 1234
1232 1231 1234 1233
1232 1233 1231 1234
1232 1233 1234 1231
1232 1234 1231 1233
1232 1234 1233 1231
1233 1231 1232 1234
1233 1231 1234 1232
1233 1232 1231 1234
1233 1232 1234 1231
1233 1234 1231 1232
1233 1234 1232 1231
1234 1231 1232 1233
1234 1231 1233 1232
1234 1232 1231 1233
1234 1232 1233 1231
1234 1233 1231 1232
1234 1233 1232 1231

---

아이디어

배열에 숫자를 입력받은 후 오름차순으로 정렬한다.

각 숫자화 true와 false를 pair로 저장하여 해당 값이 이미 정답 배열에 들어있으면 false를 아직 정답 배열에 없는 값이면 true 상태로 유지한다. 백트래킹을 하면서 정답 배열의 길이가 m가 동일해지면 정답 배열을 출력한다. 

---

알고리즘

배열에 숫자를 입력받은 후 오름차순으로 정렬한다.

각 숫자화 true와 false를 pair로 저장하여 해당 값이 이미 정답 배열에 들어있으면 false를 아직 정답 배열에 없는 값이면 true 상태로 유지한다. 재귀함수를 사용하여 정답 배열의 길이가 m과 동일해진다면 현재의 정답 배열을 출력한다.

만약 정답 배열의 길이가 m보다 짧다면 숫자를 더 넣어야 한다는 의미이므로 입력 받은 숫자 중 아직 사용하지 않은 숫자 즉, pair의 second가 true인 숫자만 정답 배열에 넣고 정답 배열의 길이가 m과 같아지는 시점까지 재귀함수를 호출한다.

정답 배열을 출력한 이후 재귀 함수를 벗어나면 마지막에 넣었던 숫자를 정답 배열에서 빼고 해당 숫자의 second를 true로 바꿔준다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m;
void print(vector<pair<int,bool>> &vec, vector<int> &ans, int cnt)
{
	if(cnt == m)
	{
		for(auto &a : ans)
			cout<<a<<" ";
		cout<<"\n";
	}
	for(auto &a : vec)
	{
		if(a.second) {
			ans.push_back(a.first);
			a.second = false;
			print(vec,ans,cnt+1);
			a.second = true;
			ans.pop_back();
		}
	}
}
int main()
{
	cin>>n>>m;
	vector<pair<int,bool>> vec;
	vector<int> ans;
	while(n--)
	{
		int temp;
		cin>>temp;
		vec.push_back({temp,true});
	}
	sort(vec.begin(), vec.end());
	print(vec,ans,0);
	return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/15654

이전에 N과 M 3번과 4번을 풀어본 기억이 있어서 조금만 응용해서 풀면 되는 문제여서 한 번에 풀 수 있었다.

역시 경험이 가장 중요한 것 같다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!