백준 1246번 온라인 판매 (JAVA)

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

1246번: 온라인 판매

 

저는 구현을 통해 문제를 해결하였습니다.

먼저 P를 오름차순으로 정렬하였습니다. i번째 사람은 P[i]이하의 가격에 사기 때문에 오름차순 정렬하고 순차적으로 접근하게 된다면, P[i]의 가격으로 뒤에 있는 사람들은 모두 사고, 앞에 있는 사람들은 안 사기 때문입니다. 

P[i] * (m-i)의 공식이 완성됩니다. 또한, 달걀의 개수가 n이기 때문에 m-i가 아무리 커도 n보다 커지면 안됩니다. 

즉, P[i] * Math.max(m-i,n)의 식이 완성되어 이를 통해 문제를 해결하였습니다.

 

package BOJ.etc;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_1246 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        List<Integer> money = new ArrayList<Integer>();
        for(int i = 0 ; i < m ; i++){
            money.add(stoi.apply(br.readLine()));
        }
        int[] result = cal(money,n,m);
        System.out.println(result[0]+" "+result[1]);
    }

    private static int[] cal(List<Integer> money, int n, int m) {
        Collections.sort(money);
        int[] result = null;
        for(int i = 0 ; i < m ; i++){
            int temp = money.get(i) * Math.min(m - i,n);
            if(result == null || result[1] < temp){
                result = new int[]{money.get(i),temp};
            }
        }
        return result;
    }
}