[백준 01758] 알바생 강호 [Java]

문제

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

 

---

풀이

대기 순번 만큼 줄어든 팁을 최대한 많이 받기 위해 손님의 순서를 바꿔야 하는 문제다.

팁 - 대기 순번이 0 이하인 경우에는 0원으로 계산하며, 대기 순번은 점점 커진다.

따라서 작은 팁이 늦은 대기 순번으로 계산할 때 더 많은 팁을 받을 수 있다.

입력받은 팁들을 내림차순으로 정렬해주자.

        // Solve
        Arrays.sort(A, Comparator.reverseOrder());        

팁 - 대기 순번의 계산 결과가 0이하가 될 때 까지 받을 수 있는 팁들을 계산하면 된다.

N은 최대 10만이며 int의 범위를 초과한다 결과는 long으로 담아주자.

         long sum = 0;
        for (int i = 0; i < N; ++i) {
            if (A[i] - i <= 0) {
                break;
            } else {
                sum += A[i] - i;
            }
        }

풀이 시간

≤ 8m

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/01758.java

problem-solving/baekjoon-online-judge/easy/01758.java at main · rogi-rogi/problem-solving