ATM (feat. 백준, 11399번)

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

11399번: ATM

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <numeric>
using namespace std;
int buf[1000];
void merge_sort(int* p, int len) {
	if (len < 2)		return;
	register int i = 0, k = 0, mid = len / 2, j = mid;
	merge_sort(p, mid);
	merge_sort(p + mid, len - mid);
	while (i < mid && j < len) {
		if (p[i] < p[j])
			buf[k++] = p[i++];
		else
			buf[k++] = p[j++];
	}
	while (i < mid)
		buf[k++] = p[i++];
	while (j < len)
		buf[k++] = p[j++];
	for (register int i = 0; i < len; ++i)
		p[i] = buf[i];
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, arr[1000], dp[1000];
	cin >> N;
	for (register int i = 0; i < N; ++i)
		cin >> arr[i];
	merge_sort(arr, N);
	dp[0] = arr[0];
	for (register int i = 1; i < N; ++i)
		dp[i] = dp[i - 1] + arr[i];
	cout << accumulate(dp, dp + N, 0);
	return 0;
}
// *&)*@*

1. 입력된 값을 오름차순으로 정렬합니다.
2. 첫번째부터 끝까지 각각의 누적합을 dp로 구합니다.
3. 구해진 dp를 모두 더해서 출력합니다.