백준 1758번 알바생 강호

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.StringTokenizer;

public class Part_Time_kangho {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Integer[] tips = new Integer[N];
        for (int i = 0; i < N; i++) {
            tips[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(tips,Collections.reverseOrder());
        long result = 0;
        for (int i = 0; i < N; i++) {
            long tip = tips[i]-i;
            if(tip<0)
                continue;
            result += tip;
        }
        System.out.println(result);
    }
}

풀이방법

일단 문제풀이 자체의 핵심은, 팁이 최댓값이 되게 하려면, 팁이 마이너스가 되는값이 최대한 많을때 최댓값이 된다. 왜냐면 마이너스가 되면 어차피 팁은 다 0이므로. 그래서 팁을 내림차순 정렬하는것이 핵심이다.

1. 팁을 내림차순 정렬한다.
2. tip에서 등수를 뺀값 -1 처리를 해주고 팁이 마이너스가 되면 팁합계에 포함하지 않는다.

여기서 주의할점.
입력값의 최대값이 N 100,000 이다. 손님이 100,000만큼오고, 온 손님 모두 팁도 100,000만큼 낸다면 1+2+....+99999+100000=100001*500000=5000050000원 값이 팁합계가 되는데, 이는 int범위를 벗어난다.
int는 32bit로 -2147483648 ~ 2147483647 범위를 가진다.
따라서 64bit인 long형을 사용해야 한다.
long형 범위 -9223372036854775808 ~ 9223372036854775807

후기

대놓고 함정문제긴 하지만, 이기회에 long, int값에 범위를 알아보게 되었다.
그리고 배열정렬시 내림차순 하는법도 익힐 수 있었다.
내림차순 정렬정도는 꼭 기억해두자