가장 쉬운거는 구현문제이다.

brute-force 방법으로 일단 풀고

DP, 최단거리, 뭐 등등 생각을 해야한다.

문제

일곱난쟁이

1. permutation으로 구현

do while로 구현

9명중에서 순서와 상관있이 순열으로 뽑아도 됨.

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

int arr[9];

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

	sort(arr, arr + 9);

	do
	{
		int sum = 0;
		for (int i = 0; i < 7; ++i) sum += arr[i];
		if (sum == 100) break;

	} while (next_permutation(arr, arr + 9));

	for (int i = 0; i < 7; ++i) cout << arr[i] << endl;

	return 0;
}

순열 재귀로 구현

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

int arr[9];

int sum = 0;
vector<int> v;

void Per(int n, int r, int d)
{
	if (sum == 100) return;

	if (r == d)
	{
		for (int i = 0; i < 7; ++i) sum += arr[i];
		if (sum == 100)
			for (int i = 0; i < 7; ++i) cout << arr[i] << "\n";
		else
			sum = 0;
	
		return;
	}

	for (int i = d; i < n; ++i)
	{
		swap(arr[i], arr[d]);
		Per(n, r, d + 1);
		swap(arr[i], arr[d]);
	}
}

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

	sort(arr, arr + 9);
	
	Per(9, 7, 0);


	return 0;
}

2. 조합으로 구현

nCr로 9명중에 7명을 뽑아서 합이 100이되는 경우와

nCr로 9명중에 2명을 뽑아 전체합 - 2명의 키 = 100이 되는 경우 두가지를 생각할 수 있겠다.

조합 재귀

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

int arr[9];

int n = 9;
int k = 7;
int sum = 0;

vector<int> c;

void combie(int start, vector<int> v)
{
	if (sum == 100) return;

	if (v.size() == k)
	{
		for (int i : v) sum += arr[i];
		if (sum == 100)
		{
			for (int i : v) cout << arr[i] << " ";
			return;
		}
		else sum = 0;

		return;
	}

	for (int i = start + 1; i < n; ++i)
	{
		v.push_back(i);
		combie(i, v);
		v.pop_back();
	}
}

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

	sort(arr, arr + 9);

	combie(-1, c);

	return 0;
}

조합 반복문 (nC(n-r))

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

int arr[9];
int cnt = 0;
int sum = 100;
int total = 0;
pair<int, int> p;

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

	sort(arr, arr + 9);

	for (int i = 0; i < 9; ++i)
		for (int j = i + 1; j < 9; ++j)
			if (total - arr[i] - arr[j] == sum)
			{
				p.first = i;
				p.second = j;
				goto result;
			}

result:
	vector<int> v;
	for (int i = 0; i < 9; ++i)
	{
		if (p.first == i || p.second == i) continue;
		
		v.push_back(arr[i]);
	}

	sort(v.begin(), v.end());
	for (int i : v) cout << i << "\n";

	return 0;
}

3. 정리

순열으로 푸는 방법은

• 재귀로 순열을 구현해서 풀기
• 반복문으로 순열을 구현해서 풀기

조합으로 푸는 방법은

• 재귀로 조합구현해서 풀기
• 반복문으로 조합 구현해서 풀기

위의 코드를 다 분석하고 이해할 수 있도록 하자잇!!