[ 백준 / BOJ 1487 ] 물건 팔기 ( 자바 / JAVA )

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

1487번: 물건 팔기

 

문제

---

세준이는 오랜 연구기간 끝에 신상품을 내놓았다. 세준이는 오랜 시간이 걸린 만큼 이 상품을 최대 이익에 팔려고 한다.

세준이는 이 상품을 사려고 하는 사람들이 총 몇 명이나 되는지 알아봤다. 무려 N명이나 살 의향을 보였다. 각각의 사람은 자기가 지불할 생각이 있는 최대 한도가 있다. 따라서, 어떤 사람이 20원까지 지불할 생각이 있는데, 세준이가 가격을 30원으로 책정하면 이 사람은 절대 안 살 것이고, 15원으로 책정하면 이 사람은 이 상품을 15원에 살 것이다. (단, 세준이가 안 팔수도 있다.)

그리고, 세준이는 각각의 사람에게 배달하는 비용이 얼마나 걸리는 지 알고 있다.

N명의 사람과, 각각의 사람이 지불할 용의가 있는 최대 금액과 배송비가 주어졌을 때, 세준이의 이익을 최대로 하는 가격을 출력하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 세준이의 물건을 구매할 의향이 있는 사람의 수 N이 주어진다. 이 값은 50보다 작거나 같다. 둘째 줄부터 각 사람이 지불할 최대 금액과 배송비가 공백을 사이에 두고 주어진다. 두 값은 모두 \(10^6\)보다 작거나 같은 음이 아닌 정수이고, 배송비는 0이 될 수도 있다.

출력

---

첫째 줄에 최대 이익을 만들어주는 가격을 출력한다. 이익이 최대인 가격이 여러개라면, 가장 낮은 가격을 출력한다. 또, 어떤 가격으로 팔아도 이익을 남길 수 없다면 0을 출력한다.

코드

---

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

public class Main_BOJ_1487_물건팔기 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;

        int N = Integer.parseInt(br.readLine());

        int[][] costs = new int[N][2];
        for(int i = 0 ; i < N; i++){
            stringTokenizer = new StringTokenizer(br.readLine());
            costs[i][0] = Integer.parseInt(stringTokenizer.nextToken());
            costs[i][1] = Integer.parseInt(stringTokenizer.nextToken());
        }

        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // TODO Auto-generated method stub
                int result = o1[0] - o2[0];
                if(result == 0)
                    result = o1[1] - o2[1];

                return result;
            }
        });

        int maxPrice = 0;
        int maxTotalPrice = 0;

        for(int i = 0 ; i < N ; i++){
            int total = 0;
            for(int j = i; j < N ;j++){
                int benefit = costs[i][0] - costs[j][1];
                if(benefit > 0)
                    total += benefit;
            }
            if(maxTotalPrice < total){
                maxTotalPrice = total;
                maxPrice = costs[i][0];
            }
        }

        System.out.println(maxPrice);
    }
}