[백준, JAVA] 1758번 : 알바생 강호

1. 문제

2. 아이디어

• (입장순서 -1)원은 어느 손님이 몇번째로 입장하는지와는 무관하다. 어차피 빼는 크기 총량은 동일하다

• 음수가 되어 팁을 주지 않는 경우의 절댓값을 최대로 만든다.
  (어차피 음수가 되어 팁을 주지 않는다면, 애초에 팁을 적게 주려고 생각했던 사람을 가장 후 순위에 배치한다.)

• 입력 값의 크기 때문에 출력 자료형은 int가 아니라 long으로 선언해야 한다.

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_4_1758{
  
    public static void main(String[] args) throws NumberFormatException, IOException {
    	BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    	int N = Integer.parseInt(bf.readLine());
    	int[] arr = new int[N+1];
    	for(int i=1; i<N+1; i++) {
    		arr[i]=Integer.parseInt(bf.readLine());
    	}
    	
    	long ans = 0;
    	Arrays.sort(arr); // 오름차순 정렬, 역순으로 체크해보자

    	for (int i = N; i > 0; i--) {
    		
    		// 맨 뒤의 값(arr[N+1]이 가장 먼저 입장(1번), 해당 인덱스의 입장 순서는(N+1)-i
    		if(arr[i]-(N+1-i-1)>0) { //음수가 아닌 경우에만 합한다.				
				ans= ans + arr[i]-(N+1-i-1);
			}
			
		}
    	System.out.println(ans);
    }
}

4. 느낀점

• 그리디 알고리즘 풀이 시, 반례나 자료형에 대해 고민해보자.