[BaekJoon] 1246 온라인 판매

1.  문제 링크

2.  문제

요약

• 고객은 각자 달걀 하나에 대한 가격을 갖고 있고, 그 가격 초과로는 사지 않습니다.
• 입력: 달걀의 개수, 고객의 수를 첫 줄에 입력 받고, 다음 줄부터는 각 고객의 가격을 입력 받습니다.
• 출력: 최대 수익을 올릴 수 있는 가장 낮은 달걀 하나 가격과 전체 수익을 출력합니다.

3.  소스코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.Collections;

public class Main {
    public Integer[] EggPrice(int n, Integer[] price) {
        Arrays.sort(price, Collections.reverseOrder());
        Integer[] result = new Integer[2];
        if(n == 1 || price.length == 1) {
            result[0] = price[0];
            result[1] = price[0];
        } else if(n < price.length) {
            int max = 0;
            int index = -1;
            
            for(int i = n - 1; i >= 0; i--) {
                int total_price = price[i] * (i + 1);
                if(max < total_price) {
                    max = total_price;
                    index = i;
                }
            }
            result[0] = price[index];
            result[1] = price[index] * (index + 1);
        } else {
            int max = 0;
            int index = -1;
            
            for(int i = price.length - 1; i >= 0; i--) {
                int total_price = price[i] * (i + 1);
                if(max < total_price) {
                    max = total_price;
                    index = i;
                }
            }
            result[0] = price[index];
            result[1] = price[index] * (index + 1);
        }
        
        return result;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Integer[] price = new Integer[m];
        for(int i = 0; i < price.length; i++) {
            price[i] = Integer.parseInt(br.readLine());
        }
        Main b = new Main();
        Integer[] result = b.EggPrice(n, price);
        for(int i = 0; i < 2; i++) {
            System.out.print(result[i] + " ");
        }
    }
}

4.  접근

1. 달걀 개수가 한 개이거나 고객이 한 명인 경우
• 입력된 가격 중 가장 높은 가격을 달걀 하나의 가격으로 합니다. 또한, 팔 수 있는 달걀 개수가 한 개이므로 최대 수익은 달걀 하나의 가격과 같습니다.
2. 고객의 수가 달걀의 수보다 많은 경우
• 만약 고객의 수가 달걀의 수보다 많다면, 전체 달걀을 팔 수 있으니, 가격을 기준으로 내림차순 되어 있는 ArrayList를 이용하여 (달걀의 수)번째 요소부터 가장 높은 가격까지 체크합니다.
• 이 때, 최대 수익을 벌 수 있는 최소의 달걀 가격을 구해야하는데, 만약 두 고객의 가격 사이의 가격을 달걀 가격으로 잡는다면, 팔 수 있는 개수는 두 고객 중 더 높은 가격일 경우와 같은데 달걀 가격은 높은 가격일 때보다 적으므로 최대 수익을 벌 수 없어 이 경우는 생각하지 않습니다.
• 이러한 접근을 기반으로 각 고객들의 가격에 대해서만 생각하고, 팔 수 있는 달걀의 수는 낮은 가격에서 높은 가격으로 올라갈수록 하나씩 감소합니다.
• 가장 낮은 가격부터 가장 높은 가격까지 계산해보고 최대 수익을 벌 수 있을 때의 달걀 한 개의 가격과 전체 수익을 반환합니다.
3. 고객의 수가 달걀의 수보다 적을 경우
• 만약 고객의 수가 달걀의 수보다 적다면, 전체 달걀을 팔 수 없고 최대로 전체 사람의 수만큼 달걀을 팔 수 있습니다.
• 그렇기 때문에 가장 낮은 가격에서부터 가장 높은 가격까지 팔 수 있는 달걀의 개수에 맞춰서 전체 수익을 계산해보고 최대 수익을 내는 달걀 한 개의 가격을 찾아냅니다.
• 찾아낸 달걀 한 개의 가격과 전체 수익을 반환합니다.