[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1758번, 알바생 강호

문제 링크

1758번: 알바생 강호

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 강호는 팁을 받는 양이 순서에 따라 달라집니다.

2. 손님의 순서를 적절히 바꾸었을 때 강호가 받을 수 있는 팁의 최대값을 결과로 출력합니다.

3. 팁의 값이 음수가 되면 팁을 받을 수 없습니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 팁 가격 기준 정렬한 뒤, 높은 팁부터 순서대로 입장시킵니다.

 

3. 모든 손님이 입장한 뒤 강호가 받은 팁의 합을 결과로 출력합니다.

 

 

팁 받기

 

순서가 뒤로 밀릴수록 많은 양의 팁이 감소해서 음수가 되기 쉽기 때문에

 

팁의 양이 클수록 먼저 입장을 해야합니다.

 

예제입력 3.

 

1. 입력된 정보를 저장합니다.

 

N = 5

 

팁의 정보

	손님 1	손님 2	손님 3	손님 4	손님 5
팁	7	8	6	9	10

 

2. 팁 가격 기준 정렬한 뒤, 높은 팁부터 순서대로 입장시킵니다.

 

팁 기준 정렬

	손님 3	손님 1	손님 2	손님 4	손님 5
팁	6	7	8	9	10

 

 

높은 팁을 주는 손님부터 순서대로 입장!

 

손님 5 ▶ 손님 4 ▶ 손님 2 ▶ 손님 1 ▶ 손님 3

 

손님 5 : 10 - (1 -1) = 10

손님 4 : 9 - (1 - 2) = 8

손님 3 : 8 - (1 - 3) = 6

손님 2 : 7 - (1 - 4) = 4

손님 1 : 6 - (1 - 5) = 2

 

 

3. 모든 손님이 입장한 뒤 강호가 받은 팁의 합을 결과로 출력합니다.

 

손님에게 받은 팁 : 10 + 8 + 6 + 4 + 2 = 30

30을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• Arrays.sort를 이용하여 팁의 금액 기준 오름차순 정렬하였습니다.
• 팁의 가격이 높은 손님부터 차례대로 입장하여 팁을 받습니다.
• 모든 팁을 받은 후 합을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        long answer = 0;
        int[] tips = new int[N];
        //각 손님의 팁 정보 저장
        for (int i = 0; i < N; i++)
            tips[i] = Integer.parseInt(br.readLine());
        Arrays.sort(tips);	//오름차순 정렬
        //팁 가격 높은 순으로 순서대로 입장
        for (int i = N-1; i >= 0 ; i--){
            int tip = tips[i] - (N-i-1);	//팁 구하기
            if(tip > 0)	//팁이 양수일 때 팁 받기
                answer += tip;
        }
        bw.write(answer + "");	//받은 팁의 합 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}