No older revisions available
No older revisions available
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();
}
- 알고리즘이 왜 빨리빨리 안 떠오르는 걸까
- 요것도 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);
}
