- 막 알고리즘 생각하다가..
~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];
}