[Baekjoon] 1758 - 알바생 강호

📝 문제

 

 

🔑 풀이 과정

· 한 사람이 내는 팁: 원래 주려고 생각했던 돈 - (받은 등수 - 1)

등수가 뒤로 갈수록 차감되는 팁의 액수가 많아진다.

즉, 강호가 최대로 팁을 받으려면, 팁의 액수가 큰 사람일수록 앞 등수에 배치해야 한다.

 

· 팁을 내림차순으로 정렬한 뒤, 원래 주려고 생각했던 돈 - (받은 등수 - 1) 식을 사용해서 팁의 총액을 계산한다.

주의해야 할 점은, 계산된 팁이 음수라면 강호는 팁을 받을 수 없다는 점이다. → 식의 결과가 음수라면 팁이 0원

 

 

🔓 답안

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

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

        //입력
        int N = Integer.parseInt(br.readLine()); //사람의 수

        ArrayList<Integer> tips = new ArrayList<>(); //팁의 액수를 넣을 ArrayList
        for(int i = 0; i < N; i++){ //N명의 팁 액수 입력받기
            tips.add(Integer.parseInt(br.readLine()));
        }
        //입력 종료

        //팁 액수 내림차순 정렬
        Collections.sort(tips, Collections.reverseOrder());

        long sum = 0; //팁의 총액을 계산할 변수
        for(int i = 1; i <= N; i++){
            int tip = tips.get(i-1) - i + 1;
            if(tip < 0) //계산한 팁이 음수라면 못받음(0원)
                sum += 0;
            else
                sum += tip;
        }

        bw.write(sum + "\n");
        bw.flush();
        bw.close();
    }

}

 

 

🖤 알고리즘 분류

- 그리디 알고리즘

- 정렬