백준 1758번 <알바생 강호>

백준 알고리즘 1758번

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

1758번: 알바생 강호

---

1758번

강호가 받을 수 있는 팁의 최댓값을 구하여라.

팁은 각자가 주려고 했던 팁에서 자신이 음료를 받은 순서 - 1 만큼 받을 수 있다.

 

입력으로 첫 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. 그 다음 N개의 줄에 걸쳐 각 사람들이  주고 싶은 팁이 주어진다.

 

출력으로 강호가 받을 수 있는 팁의 최댓값을 출력하여라.

---

문제 해결

그리디 알고리즘을 이용해 해결할 수 있다.

팁을 가장 많이 주는 사람을 가장 먼저 주면 된다. 가장 많이 주는 사람의 팁에서 조금 깎는 게 가장 많이 받을 수 있다.

또한 팁을 조금 주는 사람을 0으로 만드는 것이 팁을 많이 주는 사람을 0으로 만드는 것보다 많이 받을 수 있다.

 

N과 팁은 100,000보다 작거나 같은 자연수이다. 따라서 최대일 경우에 100,000명이 모두 100,000원을 팁으로 준다고 할 수 있고, 이때 최대로 받을 수 있는 값은 100,000*100,000-100,000 = 약 100억,, 

따라서 int 자료형을 사용하지 않고 long 자료형을 사용해야 한다.

---

코드

package bj1758;

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		long[] people = new long[N];
		for (int i = 0; i < N; i++) {
			people[i] = Integer.parseInt(br.readLine());
			people[i] *= -1;
		}
		Arrays.sort(people);
		long answer = 0;
		for (int i = 0; i < N; i++) {
			long temp = people[i] * (-1) - i;
			temp = Math.max(0, temp);
			answer += temp;

		}
		System.out.println(answer);
	}

}

---

결과

---