백준 11399번: ATM

백준 온라인 저지(BOJ) 11399번 문제

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

1. 문제 요약

ATM 1대와 그를 이용하려는 N명의 사람이 있다.

사람들 각각의 사용시간이 주어질 때, ATM을 이용하는 순서에 따라 소요시간의 합이 달라지게 된다.

소요시간의 합의 최솟값을 구하여라.

2. 알고리즘

만약 3명이라고 치자.

처음 사용하는 사람은 a분, 두번째는 b분, 세번째는 c분 소요된다고 했을 때

총 소요시간은 $(a) + (a+b) + (a+b+c) = 3a + 2b + c$이다.

앞의 상수 3, 2, 1...은 고정이므로 곱해지는 숫자인 a, b, c가 내림차순이어야 최소가 된다.

짜기 귀찮아서 걍 algorithm에 있는 sorting 씀

3. 코드

#include <iostream>
#include <algorithm>

int main() {
	int N;
	scanf("%d", &N);
	int* arr = new int[N];

	for (int i = 0; i < N; ++i) {
		scanf("%d", arr + i);
	}

	std::sort(arr, arr + N);

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

	printf("%d\n", time);

	delete[] arr;

	return 0;
}