링크 : https://www.acmicpc.net/problem/11399
정렬. 그리티 탐색 문제.
작은 순서대로 배열해야 최솟값이 나올 것 같다. 시작해보자. 그럼 이걸 어떻게해야 작은 순서대로 정렬할 수 있을까? 자료구조 문제이다.
Ver 1.
#include<iostream>
#include<algorithm>
using namespace std;
int arr[1001], sum[1001], result[1001];
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int N;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
sort(arr,arr+N);
result[0] = sum[0] = arr[0];
for (int i = 1; i < N; i++) {
sum[i] = arr[i] + sum[i - 1];
result[i] = result[i - 1] + sum[i];
}
cout <<result[N-1];
return 0;
}
Ver 2.
#include<iostream>
#include<algorithm>
using namespace std;
int arr[1001], sum[1001];
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int N;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
sort(arr,arr+N);
sum[0] = arr[0];
int tmp = sum[0];
for (int i = 1; i < N; i++) {
tmp = sum[i] = arr[i] + tmp;
sum[i] = sum[i - 1] + sum[i];
}
cout <<sum[N-1];
return 0;
}
sort하는 것은 알고리즘 라이브러리의 힘을 빌렸다.
result[0] = sum[0] = arr[0];
for (int i = 1; i < N; i++) {
sum[i] = arr[i] + sum[i - 1];
result[i] = result[i - 1] + sum[i];
}
이 부분은 피보나치 수열처럼 접근할 수 있었다. 하지만 result 배열을 사용하지 않고 사용할 수 있지 않을까? 고민해보자.
해서
sum[0] = arr[0];
int tmp = sum[0];
for (int i = 1; i < N; i++) {
tmp = sum[i] = arr[i] + tmp;
sum[i] = sum[i - 1] + sum[i];
}
tmp 변수를 사용했다. 당연한 소리지만 int 변수 하나 선언해서 사용하는 것이 배열 1001개 선언하는 것보다 더 효율적이다.