https://www.acmicpc.net/problem/11399
11399번: ATM
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
www.acmicpc.net
-Python
_ = int(input())
people = list(map(int, input().split()))
s_people = sorted(people)
sum_p = acc = 0
for i in s_people:
sum_p += acc + i
acc += i
print(sum_p)-C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
int n;
int a;
int acc = 0;
int sum = 0;
vector<int> v;
cin >> n;
for (int i = 0; i < n;i++) {
cin >> a;
v.push_back(a);
}
sort(v.begin(), v.end());
for (int i = 0;i < n;i++) {
sum += acc + v[i];
acc += v[i];
}
cout << sum;
}-풀이
아주아주 쉬운 greedy algorithm이다.
시간의 합이 최소가 되기 위해서는 입력된 시간이 오름차순으로 정렬되어 있으면 된다.
python은 list sort를 이용했고, c++은 vector sort를 이용했다.
나는 acc 변수를 이용해서 누적값을 더해줬는데, 다른 사람의 풀이를 보니 n개일 때 i번째 시간은 n-i번 더해진다라는 개념으로 접근했다.