사람들이 소요하는 시간이 오름차순이 되어야 누적합이 최소가 된다.
map <고객번호, 소요시간> 으로 받고,
소요시간 기준(map의 value) 으로 오름차순이 되도록 정렬한다.
map<int,int> → vector<pair<int,int>> 변환
vector<pair<int,int>> v(bmap.begin(), bmap.end()); // map -> vector
sort() 함수에 비교함수 작성
bool comp(pair<int,int> &left, pair<int,int> &right){
if(left.second < right.second) return true;
else return false;
}
sort(v.begin(), v.end(), comp); // value 기준으로 오름차순 정렬
vector를 순회하며 각각에 대한 누적 합을 acc_vec 벡터에 저장했다.
acc_vec 벡터의 누적합은 accumulate() 함수로 구한다.
answer = accumulate(acc_vec.begin(), acc_vec.end(), 0); // 마지막 인자는 합의 초기값
#include <bits/stdc++.h>
using namespace std;
int n, input;
long long accum, answer;
map<int, int> bmap;
vector<int> acc_vec; // 누적합을 저장
bool comp(pair<int,int> &left, pair<int,int> &right){
if(left.second < right.second) return true;
else return false;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> input;
bmap.insert({i, input});
}
vector<pair<int,int>> v(bmap.begin(), bmap.end()); // map -> vector
sort(v.begin(), v.end(), comp); // value 기준으로 오름차순 정렬
for(auto i : v){
accum += i.second;
acc_vec.push_back(accum);
}
answer = accumulate(acc_vec.begin(), acc_vec.end(), 0); // 마지막 인자는 합의 초기값
cout << answer;
return 0;
}
728x90
'알고리즘 > 백준' 카테고리의 다른 글
| 색종이 만들기 백준 2630번 c++ (0) | 2022.02.20 |
|---|---|
| 최소 힙 백준 1927번 c++ (0) | 2022.02.19 |
| 나는야 포켓몬 마스터 이다솜 백준 1620번 c++ (0) | 2022.02.19 |
| 최대 힙 백준 11279번 c++ (0) | 2022.02.19 |
| 집합 백준 11723번 c++ (0) | 2022.02.19 |