[LeetCode] 2144. Minimum Cost of Buying Candies With Discount - 문제풀이

Description

주어진 배열에는 사탕 각각 가격이 있고 두개의 사탕을 살 경우 그 가격보다 낮은 가격의 사탕을 하나 더 주는 경우 최소 구매 가격을 구하는 문제입니다.

A shop is selling candies at a discount. For every two candies sold, the shop gives a third candy for free.

The customer can choose any candy to take away for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought.

• For example, if there are 4 candies with costs 1, 2, 3, and 4, and the customer buys candies with costs 2 and 3, they can take the candy with cost 1 for free, but not the candy with cost 4.

Given a 0-indexed integer array cost, where cost[i] denotes the cost of the ith candy, return the minimum cost of buying all the candies.

Example 1:

Input: cost = [1,2,3]
Output: 5
Explanation: We buy the candies with costs 2 and 3, and take the candy with cost 1 for free.
The total cost of buying all candies is 2 + 3 = 5. This is theonly way we can buy the candies.
Note that we cannot buy candies with costs 1 and 3, and then take the candy with cost 2 for free.
The cost of the free candy has to be less than or equal to the minimum cost of the purchased candies.

Example 2:

Input: cost = [6,5,7,9,2,2]
Output: 23
Explanation: The way in which we can get the minimum cost is described below:
- Buy candies with costs 9 and 7
- Take the candy with cost 6 for free
- We buy candies with costs 5 and 2
- Take the last remaining candy with cost 2 for free
Hence, the minimum cost to buy all candies is 9 + 7 + 5 + 2 = 23.

Example 3:

Input: cost = [5,5]
Output: 10
Explanation: Since there are only 2 candies, we buy both of them. There is not a third candy we can take for free.
Hence, the minimum cost to buy all candies is 5 + 5 = 10.

Constraints:

• 1 <= cost.length <= 100
• 1 <= cost[i] <= 100

Solution 1. Sort

public int minimumCost(int[] cost) {
    int len = cost.length;
    Arrays.sort(cost);
    int cnt = 0;
    int sum = 0;
    for (int i = len-1; i >= 0; i--) {
        cnt++;
        if(cnt==3){
            cnt=0;   // get free
        }else{
            sum += cost[i];
        }
    }
    return sum;
}

구입한 두개의 사탕 각각의 가격의 최소값보다 낮은 가격을 무료로 하나 받을 수 있으니 정렬한 뒤에 가장 비싼 사탕 두개를 구입하고 그다음 비싼 사탕을 free로 받는 식으로 가격을 계산해 나갑니다.

Reference

Minimum Cost of Buying Candies With Discount - LeetCode