#1246 : 온라인 판매

풀이방법

사용된 것:

정렬

 

2022.06.12

각 가격에 대하여, 그 가격에 팔 수 있는 달걀의 개수는

(그 가격 이상을 지불할 의사가 있는 사람의 수) 와 (경래가 가지고 있는 달걀의 총 개수) 중 작은 쪽이다.

 

M명의 사람이 제시한 값 M개에 대하여 각각 위의 방법으로 팔 수 있는 개수를 구한다.

그 결과값이 가장 클 때를 찾고,

결과값이 가장 클 때의 가격이 여러 가지라면 그 중 가장 싼 쪽을 정답으로 택한다.

 

코드

Java(2022.06.12)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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());
		int[] arr = new int[m];
		
		for(int i=0; i<m; i++) arr[i] = Integer.parseInt(br.readLine());
		
		Arrays.sort(arr);
		//문제해결
		TreeSet<Integer> ts = new TreeSet<Integer>();	//수익이 가장 많을 때의 달걀당 가격을 저장할 트리셋
		int max = -1;	//달걀 판매 총 수익의 최댓값
		for(int i=0; i<m; i++) {
			int cnt = Math.min(m-i, n);	//arr[i]원에 팔 수 있는 달걀 개수
			if(max>cnt*arr[i]) continue;	//최댓값보다 비싸게 못 팔면 그냥 넘기기
			if(max<cnt*arr[i]) ts.clear();	//최댓값보다 비싸게 팔 수 있으면 ts 초기화
			ts.add(arr[i]);	//최댓값 이상에 팔 수 있으면 ts에 이번 가격을 추가
			max = Math.max(max, cnt*arr[i]);	//최댓값 업데이트
		}
		//정답 출력
		System.out.print(ts.first() + " " + max);
	}

}