문제

ATM

풀이

가장 적게 인출하는데 걸리는 시간을 구하기 위해서는 활동 선택 문제에서 풀었던 것처럼 종료 지점을 기준으로 오름차순으로 정의하고 시작지점을 종료지점에 가깝게 설정하면 되는데
이 경우에는 바로 시작됨으로 종료 지점의 오름차순으로만 정렬하고 누적합의 개수를 더한다.

사실 이게 활동 선택 문제로 바로 읽히진 않았고 문제를 이해하는데 시간이 걸렸다

1. 정렬 후 누적합의 개수를 더해준다

		Arrays.sort(arr);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += arr[i] * (n - i);
        }

정렬 후 [1,2,3,4,5] 인경우
1은 5번, 2는 4번, 3은 3번 4는 2번 5번은 1번 곱해 진다

1 --------- i=0, arr[0]
1 2 ------- i=1, arr[1]
1 2 3 ----- i=2, arr[2]
1 2 3 4 --- i=3, arr[3]
1 2 3 4 5 - i=4, arr[4]

이 규칙을 가진 누적합을 전부 더해주면 다음과 같은 점화식이 나온다
sum += arr[i] * (n - i);

전체 코드

전체 코드