U E D R , A S I H C RSS

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



1. 상규, 재동

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

struct InputData
{
	int n;
	int weight[1000];
};

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

void input()
{
	cin >> numberOfData;

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

void process()
{
	InputData temp;
	int totalWeight;
	bool flag;
	for(int i=0;i<numberOfData;i++)
	{
		temp = inputData[i];
		totalWeight = 0;
		sort(&temp.weight[0],&temp.weight[inputData[i].n]);
		flag=false;
		for(int j=0;j<inputData[i].n;j++)
		{
			if(temp.weight[j]!=inputData[i].weight[j])
			{
				if(flag == false)
				{
					totalWeight+=temp.weight[j];
					flag=true;
				}
				totalWeight+=temp.weight[j];
			}
		}
		outputData[i]=totalWeight;
	}
}

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

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

2. 인수

  • 막 알고리즘 생각하다가..
  • ~cpp TestCase를 살펴보다 보니, 열라 어이없는 규칙을 발견하고 맘.
  • 30분만에 끝남

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

int doJob(vector<int>& weights);
int getMin(vector<int>& weights, vector<int>& sortedWeights);
bool isSamePos(vector<int>& weights, vector<int>& sortedWeights, int nth);

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

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

	return 0;
}

int doJob(vector<int>& weights)
{
	vector<int> sortedWeights(weights);
	sort(sortedWeights.begin(), sortedWeights.end());

	int ret = 0;
	for(int i = 0 ; i < weights.size() ; ++i)
	{
		if(!isSamePos(weights, sortedWeights, i))
			ret += sortedWeights[i];
	}
	ret += getMin(weights, sortedWeights);
	return ret;
}

int getMin(vector<int>& weights, vector<int>& sortedWeights)
{
	for(int i = 0 ; i < weights.size() ; ++i)
	{
		if(!isSamePos(weights, sortedWeights, i))
			return sortedWeights[i];
	}
	return 0;
}

bool isSamePos(vector<int>& weights, vector<int>& sortedWeights, int nth)
{
	return sortedWeights[nth] == weights[nth];
}


Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:09
Processing time 0.0100 sec