문제
https://www.acmicpc.net/problem/11399
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
String[] input = bf.readLine().split(" ");
int[] times = new int[N];
for (int i = 0; i < N; i++) {
times[i] = Integer.parseInt(input[i]);
}
Arrays.sort(times);
int result = 0;
int prev = 0;
for (int i = 0; i < N; i++) {
result += prev + times[i];
prev += times[i];
}
System.out.println(result);
}
}
풀이 방법
- 대기 시간을 내림차 순으로 정렬한다.
- 누적합을 구한다.
핵심 포인트
- 데이터에 대한 최소 누적합을 구하는 문제이기 때문에 반드시 내림차순으로 정렬 후 문제를 해결해야한다.
보완할 점 / 느낀 점
- 문제 자체는 쉬운 문제이나, 처음 문제를 풀 때 누적합을 구하는 부분을 이중 for문을 통해 구했었다. (각 구간별 합을 구해서 더하는 방법)
- 통과는 하였으나, 분명 O(n)으로 해결할 방법이 있을 것 같아 방법을 수정하였다.
- 누적합을 구하는 알고리즘에 대해서 확실히 숙지할 필요가 있다.