1246번 : 온라인 판매

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

1246번: 온라인 판매

 

 

문제

 

 

소스코드

package com.company;

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt(); sc.nextLine();
        Integer arr[] = new Integer[m];
        for(int i=0;i<m;i++) {
            arr[i] = Integer.parseInt(sc.nextLine());
          //arr[i] = sc.nextInt(); sc.nextLine();
        }
        Arrays.sort(arr, Collections.reverseOrder());

        int price=0; //책정 가격
        int max=0; //올릴 수 있는 최대 수익
        int minIdx = Math.min(n,m);

        for(int i=0;i<minIdx;i++) {
            if (arr[i] * (i + 1) > max) { //이전 수익보다 더 높을 경우
                price = arr[i];
                max = arr[i] * (i + 1);
            }
        }

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

 

 

해결방법

이분 탐색을 이용해 풀려고 하였는데 뭔가 좀 아닌 것 같아 문제를 다시 읽어보았다.

"한 고객에게 두 개 이상의 달걀은 팔지 않기로 하였다." 이 말의 즉슨 한 고객에게 무조건 하나의 달걀만 판다는 말이었다.

이러면 매우 간단해진다. 달걀의 수와 고객의 수를 기준으로 나올 수 있는 최댓값만 구하면 되기 때문이다. 근데 여기서 하나 더 유의할 점이 있는데 

달걀(N)이 5개여도 고객(M)이 4명이면 4개만 팔 수 있다.
고객(M)이 5명이어도 달걀(N)이 4개면 4개만 팔 수 있다.
=> 달걀(N)과 고객(M)중 최솟값에 맞춰 계산해야한다.

이 점을 유의하여 코드를 작성해주면 문제를 해결할 수 있다.

 

예시

달걀 5개, 고객 4명
2 7 8 10

1개 판매 시 최대 이익(10원으로 판매): 10
2개 판매 시 최대 이익(8원으로 판매): 16
3개 판매 시 최대 이익(7원으로 판매): 21
4개 판매 시 최대 이익(2원으로 판매): 8

=> 21