4. 백준 15663 N과 M (9)

문제 설명

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- N개의 자연수 중에서 M개를 고른 수열을 출력한다.
- 중복되는 수열을 여러 번 출력하면 안 된다.
- 각 수열은 공백으로 구분해서 출력한다.
- 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

입력

첫째 줄: N과 M (1 ≤ M ≤ N ≤ 8)
둘째 줄: N개의 수 (각 수는 10,000 이하의 자연수)

 

출력

조건을 만족하는 수열을 한 줄에 하나씩 출력한다.

 

예제 입력1

4 2
9 7 9 1

 

예제 출력1

1 7
1 9
7 1
7 9
9 1
9 7
9 9

 

 

문제 - 재귀 사용 X

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int n, r, t;
vector<int> v;
set<vector<int>> s;

template <typename T>
bool my_next_permutatioin(T first, T last)
{
	
}

int main()
{
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL); cout.tie(NULL);

	
    
	return 0;
}

 

문제 - 재귀 사용 O

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int n, r, t;
vector<int> v;
set<vector<int>> s;

void printV(vector<int>& v)
{
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << "\n";
}

void makePermutation(int n, int r, int depth)
{

}

int main()
{
	ios_base::sync_with_stdio(NULL);
	cin.tie(false); cout.tie(false);



	return 0;
}

 

정답 - 재귀 사용 X

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int n, r, t;
vector<int> v;
set<vector<int>> s;

template <typename T>
bool my_next_permutatioin(T first, T last)
{
	if (first == last) return false;
	T i = last;
	if (first == --i) return false;

	while (true)
	{
		T i1 = i;
		if (*--i < *i1) {
			T i2 = last;
			while (!(*i < *--i2));
			iter_swap(i, i2);
			reverse(i1, last);
			return true;
		}
		if (i == first) {
			reverse(first, last);
			return false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n >> r;

	for (int i = 0; i < n; i++) {
		cin >> t;
		v.push_back(t);
	}

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

	do {
		vector<int> sv;
		for (int i = 0; i < r; i++) {
			sv.push_back(v[i]);
		}
		s.insert(sv);
	} while (my_next_permutatioin(v.begin(), v.end()));

	// 중복 제거
	for (std::set<vector<int>>::iterator it = s.begin(); it != s.end(); ++it) {
		for (int i = 0; i < r; i++) {
			cout << (*it)[i] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

 

정답 - 재귀 사용 O

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

int n, r, t;
vector<int> v;
set<vector<int>> s;

void printV(vector<int>& v) {
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << '\n';
}

// n개중에 r개를 뽑는다
void makePermutation(int n, int r, int depth)
{
	
	if (r == depth)
	{
		// debugging 용
		//printV(v);
		vector<int> sv;
		for (int i = 0; i < r; i++) {
			sv.push_back(v[i]);
		}
		s.insert(sv);
		return;
	}
	for (int i = depth; i < n; i++) {
		swap(v[i], v[depth]);
		makePermutation(n, r, depth + 1);
		swap(v[i], v[depth]);
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n >> r;

	for (int i = 0; i < n; i++) {
		cin >> t;
		v.push_back(t);
	}

	makePermutation(n, r, 0);

	// 중복 제거
	for (std::set<vector<int>>::iterator it = s.begin(); it != s.end(); ++it) {
		for (int i = 0; i < r; i++) {
			cout << (*it)[i] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

 

호출 스택

m(4, 4, 0)

	i=0
	s(0, 0)
	m(4, 4, 1)
	
		i=1
		s(1, 1)
		m(4, 4, 2)
		
			i = 2
			s(2, 2)
			m(4, 4, 3)
			
				i=3
				s(3, 3)
				m(4, 4, 4)
					p=> 9 7 9 1
				s(3, 3)
				
			s(2, 2)
			
			i = 3
			s(2, 3)
			m(4, 4, 3)
			
				s(3, 3)
				m(4, 4, 4)
					p=> 9 7 1 9
				s(3, 3)
				
			s(3, 2)
			
		s(1, 1)
		
		i=2
		s(2, 1)
		m(4, 4, 2)
		
			i=2
			s(2, 2)
			m(4, 4, 3)
			
				i=3
				s(3, 3)
				m(4, 4, 4)
					p=> 9 9 7 1
				s(3, 3)
				
			s(2, 2)
			
			i=3
			s(3, 2)
			m(4, 4, 3)
			
				i=3
				s(3, 3)
				m(4, 4, 4)
					p=> 9 9 1 7
				s(3, 3)
				
			s(3, 2)
		s(2, 1)
		
		i=3
		s(3, 1)
		m(4, 4, 2)
			
			i=2
			s(2, 2)
			m(4, 4, 3)
			
				i=3
				s(3, 3)
				m(4, 4, 4)
					p=> 9 1 9 7
				s(3, 3)
			s(2, 2)
			
			i=3
			s(3, 2)
			m(4, 4, 3)
			
				i=3
				s(3, 3)
				m(4, 4, 4)
					p=> 9 1 7 9
				s(3, 3)
			s(3, 2)
		s(3, 1)
	s(0, 0)
	
	i=1
	s(1, 0)
	m(4, 4, 1)
	
		i=1
		s(1, 1)
		m(4, 4, 2)
		
			i=2
			s(2, 2)
			m(4, 4, 3)
			
				i=3
				s(3, 3)
				m(4, 4, 4)
					p=> 7 9 9 1
				s(3, 3)
			s(2, 2)
			
			i=3
			s(3, 2)
			m(4, 4, 3)
				
				i=3
				s(3, 3)
				m(4, 4, 4)
					p=> 7 9 1 9
				s(3, 3)
			s(3, 2)
		s(1, 1)
		
		i=2
		s(2, 1)
		m(4, 4, 2)
		
			i=2
			s(2, 2)
			m(4, 4, 3)
			
				i=3
				s(3, 3)
				m(4, 4, 4)
					p=> 7 9 9 1
				s(3, 3)
			s(2, 2)
			
			i=3
			s(3, 2)
			m(4, 4, 3)
				
				i=3
				s(3, 3)
				m(4, 4, 4)
					p=> 7 9 1 9
				s(3, 3)
			s(3, 2)
		s(2, 1)
		
		i=3
		s(3, 1)
		m(4, 4, 2)
			
			i=2
			s(2, 2)
			m(4, 4, 3)
			
				i=3
				s(3, 3)
				m(4, 4, 4)
					p=> 7 1 9 9
				s(3, 3)
			s(2, 2)
			
			i=3
			s(3, 2)
			m(4, 4, 3)
			
				i=3
				s(3, 3)
				m(4, 4, 4)
					p=> 7 1 9 9
				s(3, 3)
			s(3, 2)
		s(3, 1)
	s(1, 0)
	
	i=2
	s(2, 0)
	m(4, 4, 1)
...