백준 11399: ATM

문제 요약

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

뒷사람이 돈을 인출하는 데에는 앞사람이 걸린 시간과 자신이 인출하는 데에 걸리는 시간이 누적되어 계산된다.

문제 분류

• 그리디 알고리즘
• 정렬

문제 풀이

결국 시간이 가장 적게 걸리는 사람순으로 정렬하여 구하면 된다. 앞사람부터 누적시켜야 하므로 누적시키는 변수가 하나 더 필요할 것이다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	int n, in, sum = 0, res = 0;
	vector<int> v;
	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%d", &in);
		v.push_back(in);
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < n; i++) {
		sum += v[i];
		res += sum;
	}
	cout << res;
	return 0;
}