문제 : https://www.acmicpc.net/problem/11399

서론

분류가 그리디 알고리즘으로 되어있는데, 그리디 알고리즘에 대한 개념이 없어도 문제에 어떻게 풀어야하는지 친절하게 설명해주고 있다.

문제 알고리즘 내용이 운영체제 job scheduling 방식 중 이론적으로 optimal한 방식으로 배웠던것 같다.

프로세스의 소요시간을 정확히 예측할 수 없어서 어디까지나 이론이라고 들었던것 같다.

아이디어

인출하는데 걸리는 시간이 가장 빠른 사람부터 먼저 처리하는 그리디 알고리즘.

p를 오름차순 정렬한 후에 각 사람의 대기시간은 앞 사람들과 나의 소요시간을 모두 더한다.

대기열의 사람들의 대기시간을 전부 더해서 출력한다.

구현

// c++

#include <iostream>
#include <algorithm>

using namespace std;

int p[1001];
int dp[1001];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> p[i];
	sort(p, p + n);

	dp[0] = p[0];
	int result = dp[0];
	for (int i = 1; i < n; i++) {
		dp[i] = dp[i - 1] + p[i];
		result += dp[i];
	}
	cout << result;
}