2022.02.09 46일차

백준 1758번 (알바생 강호)

문제

스타박스는 손님을 입장시킬 때 독특한 방법으로 입장시킨다.

스타박스에서는 손님을 8시가 될 때 까지, 문앞에 줄 세워 놓는다. 그리고 8시가 되는 순간 손님들은 모두 입구에서 커피를 하나씩 받고, 자리로 간다. 강호는 입구에서 커피를 하나씩 주는 역할을 한다.

손님들은 입구에 들어갈 때, 강호에게 팁을 준다. 손님들은 자기가 커피를 몇 번째 받는지에 따라 팁을 다른 액수로 강호에게 준다. 각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다. 만약, 위의 식으로 나온 값이 음수라면, 강호는 팁을 받을 수 없다.

예를 들어, 민호는 팁을 3원 주려고 했고, 재필이는 팁을 2원, 주현이가 팁을 1원 주려고 한 경우를 생각해보자.

민호, 재필, 주현이 순서대로 줄을 서있다면, 민호는 강호에게 3-(1-1) = 3원, 재필이는 2-(2-1) = 1원, 주현이는 1-(3-1) = -1원을 팁으로 주게 된다. 주현이는 음수이기 때문에, 강호에게 팁을 주지 않는다. 따라서, 강호는 팁을 3+1+0=4원을 받게 된다.

스타박스 앞에 있는 사람의 수 N과, 각 사람이 주려고 생각하는 팁이 주어질 때, 손님의 순서를 적절히 바꿨을 때, 강호가 받을 수 잇는 팁의 최댓값을 구하는 프로그램을 작성하시오.

나의 풀이

1. 사람 수 N, 팁 nArr
2. nArr의 값에서 인덱스만큼 빼기, 음수일 때 0으로 처리 -> 최대값 조건
3. 내림차순으로 정렬
4. 뺀 값이 0보다 클 때 answer에 더하기

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

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());
        Integer[] nArr = new Integer[N];
        long answer = 0;

        for (int i = 0; i < N; i++) {
            nArr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(nArr, new Comparator<Integer>() {
            @Override
            public int compare(Integer i1, Integer i2) {
                return i2 - i1;
            }
        });

        for (int x = 0; x < N; x++) {
            int val = nArr[x] - x;
            if (val > 0) {
                answer += val;
            }
        }

        System.out.println(answer);
    }
}

생각하기

• 범위 주의하기
• 배열 재정렬 복습

내림차순 정렬
Arrays.sort(arr, new Comparator<Integer>() {
	@Override
    public int compare(Integer i1, Integer i2) {
    	return i2 - i1;    
	}
}