[Baekjoon] 1758_알바생 강호

Silver IV

문제(출처: https://www.acmicpc.net/problem/1758)

---

< 알바생 강호 >

 

문제 풀이 

 

팁의 최댓값을 구하기 위해서는 팁이 많은 순서대로 손님의 순서를 바꾸면 된다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class _1758_ { // 알바생 강호

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

		int n = Integer.parseInt(bf.readLine());

		PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < n; i++) {
			queue.add(Integer.parseInt(bf.readLine()));
		}

		long result = 0;
		int idx = 1;

		while (!queue.isEmpty()) {
			int num = queue.poll() - (idx++ - 1);
			if (num > 0)
				result += num;
		}

		System.out.println(result);
	}
}

 

Main

변수)
n : 사람 수
queue : 우선순위 큐
idx : 손님 순서
result : 팁의 최댓값

 

- 사람 수(n) 입력

- 각 사람이 주려고 하는 팁을 입력받아 우선순위 큐에 저장

- 우선순위 큐가 빌 때까지 반복

: 돈 - (받은 등수 idx - 1) 계산

: 계산한 값이 음수가 아니라면 result에 더함

- 팁의 최댓값(result) 출력

---

---