[백준] 자바 1758 알바생 강호

문제

스타박스는 손님을 입장시킬 때 독특한 방법으로 입장시킨다.

스타박스에서는 손님을 8시가 될 때까지, 문 앞에 줄 세워 놓는다. 그리고 8시가 되는 순간 손님들은 모두 입구에서 커피를 하나씩 받고, 자리로 간다. 강호는 입구에서 커피를 하나씩 주는 역할을 한다.

손님들은 입구에 들어갈 때, 강호에게 팁을 준다. 손님들은 자기가 커피를 몇 번째 받는지에 따라 팁을 다른 액수로 강호에게 준다. 각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다. 만약, 위의 식으로 나온 값이 음수라면, 강호는 팁을 받을 수 없다.

예를 들어, 민호는 팁을 3원 주려고 했고, 재필이는 팁을 2원, 주현이가 팁을 1원 주려고 한 경우를 생각해보자.

민호, 재필, 주현이 순서대로 줄을 서있다면, 민호는 강호에게 3-(1-1) = 3원, 재필이는 2-(2-1) = 1원, 주현이는 1-(3-1) = -1원을 팁으로 주게 된다. 주현이는 음수이기 때문에, 강호에게 팁을 주지 않는다. 따라서, 강호는 팁을 3+1+0=4원을 받게 된다.

스타벅스 앞에 있는 사람의 수 N과, 각 사람이 주려고 생각하는 팁이 주어질 때, 손님의 순서를 적절히 바꿨을 때, 강호가 받을 수 있는 팁의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같은 자연수이다.

출력

강호가 받을 수 있는 팁의 최댓값을 출력한다.

---

테스트 케이스

 

초록색 입력/검은색 출력

---

접근

여러개의 수가 주어졌을 때, 전체수에서 어떤 수를 총합에 한번 더할 때마다 전체수가 1씩 깎일 때 얻을 수 있는 최댓값을 구하는 문제입니다.

ex) 5, 3, 1이 일때 5를 채택하면 3, 1이 -1 되어 2, 0 이 됨

ex2) 4, 9, 10일 때 10을 채택하면 나머지수가 3, 8이 되어 여기서 한번 더 8을 선택하면 3은 2가 됨

 

이때, 더해진 총합이 최대가 되도록 해야 합니다.

 

이때 받은 수를 오름차순으로 정렬하여 계산한다면

1, 1, 3 일 때 일 경우 최댓값을 얻을 수 없게 됩니다. ->1

하지만, 내림차순으로 정렬하면

3, 1, 1이 되어 최댓값을 얻을 수 있습니다. ->3

---

코드

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

	/*
 	1758 problem 알바생강호
	*/
	static boolean visit[];
	static int count;
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int num = Integer.parseInt(br.readLine());
		Integer arr[] = new Integer[num];
		long result = 0;
		for(int i=0; i<num; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(arr,Collections.reverseOrder());
		for(int i=0; i<num; i++) {
			int count = arr[i] - (i+1-1);
			if(count > 0) {
				result += count;
			}
			else {
				continue;
			}
		}
		bw.write(String.valueOf(result));
		
		bw.flush();
		bw.close();
	}
}

---

주의

int 배열을 사용한 경우 Arrays.sort(arr, Collections.reverseOrder())이 오류 나게 됩니다. 

Integer를 이용해주어야 합니다.

오름차순으로 정렬하면 안 됩니다.

총 테스트 케이스 10만 개에, 안에 값이 10만까지 이므로 int를 사용하면 실패가 뜹니다 결과 타입은 long을 사용해줘야 합니다.