[C/C++] 백준 11399, Greedy

문제

11399번: ATM (acmicpc.net)

11399번: ATM

코드

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
	vector<int> time;
	int N, t, sum = 0;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> t;
		time.push_back(t);
	}
	sort(time.begin(), time.end());

	for (int i = 0; i < N; i++)
		sum += time[i] * (N - i);

	cout << sum;
}

 

풀이

1. 시간이 적게 걸리는 사람이 맨 앞에 설수록 유리하므로, 벡터time에 각 소요시간을 입력받아 오름차순으로 정렬한다.

2. 사람이 N 명일 때 총 걸리는 시간은 time[0]*(N-0) + time[1]*(N-1) + time[2]*(N-2) + ... + time[N-1]*(N-N-1) 이므로 반복문을 사용해 각각 sum=0에 더한다.