백준 - 일곱난쟁이_2번째 풀이

재귀로 풀기 240815

#include <iostream>
#include <typeinfo>
using namespace std;

#include <list>

#include <vector>
#include <algorithm>
#include <memory>
#include <sstream>
#include <map>

bool combi(vector<int>& _v, 
	vector<int>& _result , int _index)
{
	if (_result.size() == 7)
	{
		int sum = 0;
		for (auto& iter : _result)
		{
			sum += iter;
		}

		if (sum == 100)
		{
			for (auto& iter : _result)
			{
				cout << iter << endl;
			}
			return true;
		}
	}

	for (int i = _index; i < _v.size(); ++i)
	{
		_result.push_back(_v[i]);
		if (combi(_v, _result, _index + 1) 
			== true)
			return true;
		_result.pop_back();
	}

	return false;
}


int main()
{
	vector<int> v(9);

	for (int i = 0; i < 9; ++i)
	{
		cin >> v[i];
	}

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

	vector<int> result;
	combi(v, result, 0);

}

---

접근

: 9명 중에서 일곱명을 구하는 것임.

조합이다.
-> 왜냐하면 순서에 관계없이 원하는 조건의 수를 추출하는 것이므로

문제 조건으로 오름차순으로 뽑으라고 했고, 여러 정답 나오면 아무거나 출력
-> 순열( next_permutation) 으로 돌리면서 그 안에서 조건에 해당하는
벡터를 출력하는 방법으로 접근함.

코드

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
#include <algorithm>
#include <vector>



int main()
{
	vector<int> v{ 20,7,23,19,10,15,25,8,13 };

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

	do
	{
		int sum = 0;

		for (auto iter : v)
		{
			sum += iter;

			if (sum == 100)
			{
				for (int i = 0; i < 7; i++)
				{
					cout << v[i] << endl;
				}
				return 0;
			}
		}
	} while (next_permutation(v.begin(), v.end()));

	
}

답