BOJ - 2309 일곱난쟁이

문제 링크

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

시간, 공간 제한

- 시간 제한 : 2초

- 메모리 제한 : 128MB

 

초기 문제 접근 방향

1. 입력이 9이고 시간제한이 2초 이므로 모든 경우의 수를 탐색할 때 시간초과에 걸리지 않을 수 있겠다고 생각

2. 모든 경우의 수의 경우 조합으로 알 수 있음 

• 9개 중 순서에 상관없이 7개를 뽑고 뽑은 것들의 합이 100 이되면 출력하자!
• 조합은 재귀의 방식으로 구현 해보자

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int n = 9;
int k = 7;
int	a[9];

vector<vector<int> > ans;
void comb(int start, int *a, vector<int> b)
{
	if (b.size() == k)
	{
		if (accumulate(b.begin(), b.end(), 0) == 100)
			ans.push_back(b);
		return ;
	}
	for (int i = start + 1; i < n; ++i)
	{
		b.push_back(a[i]);
		comb(i, a, b);
		b.pop_back();
	}
}

int main(void)
{
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	sort(a, a + n);
	vector<int> b;
	b.reserve(7);
	ans.reserve(100);
	comb(-1, a, b);
	for (auto i : ans[0])
		cout << i << "\n";
	return (0);
}

문제 접근 다른 방향

• pre-fix sum
  • 전체 난쟁이의 키의 합을 구한뒤 2명의 난쟁이의 키를 뺐을 때 100이되면 해당 난쟁이들의 번호를 기억 해놓기
  • 구한 난쟁이 번호를 제외 하고 출력

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

int a[9];
int sum = 0;
vector<int> ans;
pair<int, int> ret;

void solve()
{
	for (int i = 0; i < 9; ++i)
	{
		for (int j = i + 1; j < 9; ++j)
		{
			if (sum - a[i] - a[j] == 100)
			{
				ret = {i, j};
				return ;
			}
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	for (int i = 0; i < 9; ++i)
	{
			cin >> a[i];
			sum += a[i];
	}
	solve();
	for (int i = 0; i < 9; ++i)
	{
		if (ret.first == i || ret.second == i)
			continue;
		ans.push_back(a[i]);
	}
	sort(ans.begin(), ans.end());
	for (auto i : ans)
		cout << i << '\n';
	return (0);
}