[edit]

1. 상규, 재동 ¶

~cpp 
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

struct InputData
{
	int n;
	int x;
	int weight[30];
};

int numberOfData;
InputData inputData[10];
bool outputData[10];

void input()
{
	cin >> numberOfData;

	for(int i = 0 ; i < numberOfData ; i++)
	{
		cin >> inputData[i].n;
		cin >> inputData[i].x;

		for(int j = 0 ; j < inputData[i].n; j++)
			cin >> inputData[i].weight[j];
	}
}

void process()
{
	for(int i = 0 ; i < numberOfData ; i++)
	{
		sort(&inputData[i].weight[0],&inputData[i].weight[inputData[i].n],greater<int>());
		int team1 = inputData[i].weight[0], team2 = inputData[i].weight[1];
		for(int j=2;j < inputData[i].n;j++)
		{
			if(team1 < team2)
				team1 += inputData[i].weight[j];
			else
				team2 += inputData[i].weight[j];
		}
		if(abs(team1 - team2) <= inputData[i].x)
			outputData[i] = true;
		else
			outputData[i] = false;
	}
}

void output()
{
	for(int i = 0 ; i < numberOfData ; i++)
		cout << outputData[i] << endl;
}

void main()
{
	input();
	process();
	output();
}

[edit]

2. 인수 ¶

알고리즘이 왜 빨리빨리 안 떠오르는 걸까
요것도 1시간 넘게 걸렸다--; 선호랑 연습을 해야 하는걸까

~cpp 
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

bool IsDividable(vector<int>& weights, int diff);
int GetMax(vector<int>& weights, int diff);
int GetMin(vector<int>& weights, int diff);

int main()
{
	int weight, diff, num;
	vector<int> weights;

	cin >> num;
	cin >> diff;

	for(int i = 0 ; i < num ; ++i)
	{
		cin >> weight;	
		weights.push_back(weight);	
	}

	if(IsDividable(weights, diff))
		cout << "Yes";
	else
		cout << "No";

	return 0;
}

bool IsDividable(vector<int>& weights, int diff)
{
	sort(weights.begin(), weights.end());
	int partTotal = 0;
	for(int i = 0 ; i < weights.size() ; ++i)
	{
		partTotal = weights[i];
		for(int j = i + 1 ; j < weights.size() ; ++j)
		{
			if(i != j)
			{
				partTotal += weights[j];
				if(partTotal < GetMin(weights, diff))
					continue;
				else if(partTotal >= GetMin(weights, diff) && partTotal <= GetMax(weights, diff))
					return true;
				else
				{
					partTotal -= (weights[j] + weights[j-1]);
					continue;
				}
				partTotal = 0;
			}
		}			
	}
	return false;
}

int GetMax(vector<int>& weights, int diff)
{
	float total = accumulate(weights.begin(), weights.end(), 0) / 2;
	return (total + diff/2);
}

int GetMin(vector<int>& weights, int diff)
{
	float total = accumulate(weights.begin(), weights.end(), 0) / 2;
	return (total - diff/2);
}

2002년도ACM문제샘플풀이

2002년도ACM문제샘플풀이/문제D

Contents

1. 상규, 재동 ¶

2. 인수 ¶