그리디 알고리즘

현재 상태에서 가장 이익이 큰 선택을 하고, 그 선택이 전체적인 최적해로 이어지길 기대하는 알고리즘. 지역 최적해(local optimum)을 선택했을 때 전체 최적해(global optimum)는 찾지 못하는 경우에는 사용할 수 없다.

주어진 문제에서는 인출에 걸린 총 시간을 구하며, 순서에 따라 결과는 변하더라도 각각의 Pi는 변하지 않으므로 오름차순으로 정렬하여 더한 값이 최솟값이 된다.

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int result;

int main()
{
    cin >> N;

    int P[N];
    int num;

    for (int i = 0; i < N; i++)
    {
        cin >> num;
        P[i] = num;
    }

    sort(P, P+N);

	for(int i = 0 ; i < N; i++) {
		for(int j = 0; j <= i; j++) {
			result += P[j];	
		}
	}

    cout << result;

}