[BOJ] 1246 온라인 판매 - JAVA

1. 문제

1246번: 온라인 판매

경래는 닭을 기르는데 올 겨울 달걀 풍년으로 함박 웃음을 짓고 있다. 그리고 이 달걀을 영양란으로 둔갑하여 옥션에 판매하려한다.
경래는 총 N개의 달걀이 있고, 그의 잠재적인 고객은 총 M명이다. 그리고 각각의 i번째 고객은 각자 달걀 하나를 Pi 가격 이하로 살 수 있다고 밝혔다.
경래는 영양란이라 속인 죄책감에 한 고객에게 두 개 이상의 달걀은 팔지 않기로 하였다. 하지만 위의 규칙 하에 수익은 최대로 올리고 싶기에 얼마로 팔지 고민하고 있다. 즉, A가격에 달걀을 판다고 하면 Pi가 A가격보다 크거나 같은 모든 고객은 달걀을 산다는 뜻이다. (물론 달걀 총 수량을 초과하여 팔 수 는 없다)
문제는 이러한 경래를 도와 최대 수익을 올릴 수 있는 달걀의 가장 낮은 가격을 책정하는 것이다.

---

2. 풀이

1.  입력받은 P배열을 오름차순으로 정렬한다.

2.  가격을 P[0]부터 P[M-1]까지 1씩 올려가면서 비교한다.

2-1.  price는 현재까지 가장 높은 한 개의 가격, total은 가장 높은 총 가격, idx는 price를 구매할 수 있는 인덱스 번호다.

2-2.  현재 가격 p가 P[idx]보다 크다면 idx를 하나씩 증가시킨다.

2-3.  total가격이 현재가격 p*Math.min(N,M-idx)보다 작다면 price와 total을 변경한다. 이 때, Math.min을 사용하는 이유는 구매할 수 있는 인원보다 달걀의 양이 더 적을 수 있기 때문이다.

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

public class BOJ_1246_온라인판매 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());

      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());

      int[] P = new int[M];
      for(int i=0;i<M;i++) P[i] = Integer.parseInt(in.readLine());
      Arrays.sort(P);

      int price = 0;
      int idx = 0;
      int total = 0;
      int tmpTotal;
      for(int p=P[0];p<=P[M-1];p++){
         while (idx<M && p >P[idx]) {
            idx++;
         }
         if(total<(tmpTotal = p*Math.min(N,M-idx))){
            total = tmpTotal;
            price = p;
         }
      }

      System.out.println(price+" "+total);
   }
}

---

3. 결과

가격을 1씩 증가시키지 않고 P배열 내에 있는 가격으로만 하다가 틀렸다.