온라인 판매

https://www.acmicpc.net/problem/1246

 

문제

경래는 닭을 기르는데 올 겨울 달걀 풍년으로 함박 웃음을 짓고 있다. 그리고 이 달걀을 영양란으로 둔갑하여 옥션에 판매하려한다.

경래는 총 N개의 달걀이 있고, 그의 잠재적인 고객은 총 M명이다. 그리고 각각의 i번째 고객은 각자 달걀 하나를 Pi 가격 이하로 살 수 있다고 밝혔다.

경래는 영양란이라 속인 죄책감에 한 고객에게 두 개 이상의 달걀은 팔지 않기로 하였다. 하지만 위의 규칙 하에 수익은 최대로 올리고 싶기에 얼마로 팔지 고민하고 있다. 즉, A가격에 달걀을 판다고 하면 Pi가 A가격보다 크거나 같은 모든 고객은 달걀을 산다는 뜻이다. (물론 달걀 총 수량을 초과하여 팔 수 는 없다)

문제는 이러한 경래를 도와 최대 수익을 올릴 수 있는 달걀의 가장 낮은 가격을 책정하는 것이다.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 입력된다. 둘째 줄부터 M+1번째 줄까지 i+1번째 줄에는 Pi(1 ≤ Pi ≤ 1,000,000)가 입력된다.

출력

첫째 줄에 경래가 책정한 가격과 이 가격으로 올릴 수 있는 수익을 출력한다.

예제 입력 1 

5 4
2
8
10
7

예제 출력 1 

7 21

 

풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        ArrayList<Integer> list = new ArrayList<>();
        
        for(int i = 0; i<M; i++){
            list.add(Integer.parseInt(br.readLine()));
        }
        
        Collections.sort(list);
        
        int revenue = 0;
        int price = 0;
        
        for(int i = 0; i< M; i++){
            int tmp = list.get(i);
            int tmpsum = 0;
            
            if(M-i<N){
                tmpsum = tmp * (M-i);
            }else{
                tmpsum = tmp * N;
            }
            if(tmpsum > revenue){
                revenue = tmpsum;
                price = tmp;
            }
        }
        System.out.print(price + " " + revenue);
    }
}

 

우선 BufferedReader 와 StringTokenizer를 사용하여 읽어온 라인을 두 숫자로 나누어 N, M 에 저장하여주었다. 그 뒤 받아온 잠재적인 고객의 숫자를 뜻하는 M 만큼 for문을 돌려 각 고객별 소비할 수 있는 최대 금액들을 list에 저장하였다. Collections.sort() 를 사용아여 오름차순 정렬을 하게되면 리스트 내에서 0번째 부터 M번째 까지 지불할수 있는 금액이 순차적으로 정렬된 것이다. 따라서 M-i 이  list.get(i) 로 가져온 tmp 가격에 살 수 있는 고객의 수 이므로 이 둘을 곱하면 수익을 구할 수 있었다. M-i < N 을 만족하지 않을 경우에는 모든 고객이 구매 가능한 상황이므로 tmp에 N 을 곱해주어 수익을 계산하였다. 이렇게 for문을 돌리면서 구한 각 상황에서의 수익인 tmpsum 을 반복문 밖에 선언해준 revenue와 비교하여 더 크다면 더 좋은 수익을 내는 경우이므로 revenue와 price 이때의 수익과 가격으로 초기화해주어 구현 할 수 있었다.