[백준] S4 1758번 알바생 강호 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

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. 각 값들을 입력받는다

2. 처음에 줄려고 생각한 팁들을 정렬해준다.

3. 정렬된 팁을 내림차순으로 생각하게 되면 가장 많은 돈을 받을 수 있다.

4. 모든 팁들을 더해주고 결과를 출력한다.

[접근]

1. 많은 팁을 줄려고 한 사람 순으로 먼저 주게 되면 많은 팁을 얻을 수 있다.

2. 내림차순으로 정렬해주고 0번부터 처리를 하려고 했다.

3. 하지만 기본 제공되는 Arrays.sort를 사용하고, 역순으로 하면 내림차순이기 때문에 해당 방법을 사용하였다.

4. 음수가 아닌 경우라면 팁을 받을 수 있으니까 해당 경우에 맞춰 처리를 해주었다.

[코드]

package BOJ_silver;

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

public class Main_S4_1758 {
	static int n; // 사람 수
	static int arr[]; // 사람들이 주는 팁을 담을 배열
	static int turn = 1; // 현재 몇번째로 받는지를 담는 변수
	static long totaltip; // 받을수 있는 팁들의 합

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 사람 수 입력받기
		n = Integer.parseInt(br.readLine());
		
		// 초기화
		arr = new int[n];
		
		// 팁들을 입력받기
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		// 팁들을 정렬하기 >> 이렇게 하면 오름차순 정렬이 되는데 역순으로 사용하면 되므로 따로 정렬을 재정의 하지 않았다.
		Arrays.sort(arr);
		
		// 역순으로 반복
		for (int i = arr.length - 1; i >= 0; i--) {
			// 팁 : 줄려고 한 돈 - (자신의 차례 - 1)
			int tip = arr[i] - (turn - 1);
			// 만약에 팁이 0보다 크다면 (음수가 아니라면)
			if (tip >= 0)
				totaltip += tip; // 더하기
			turn++; // 턴은 계속 증가
		}
		
		// 총 받을 수 있는 팁을 출력하기
		System.out.println(totaltip);
	}
}