[백준] 1246 - 온라인 판매

1. 문제

1246번: 온라인 판매

2. 개요

N개의 달걀, M명의 잠재 고객이 있다.

i번째 고객은 Pi이하의 가격을 지불하고 달걀을 살 의향이 있다.

고객 1명당 달걀 1개까지 판매할 수 있을 때, 최대 수입을 올릴 수 있는 달걀 가격과 총 수입을 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

고객의 가격정보를 받으며 배열에 저장한 뒤, 이를 오름차순으로 정렬한다.

0번 인덱스부터 탐색하며 M - i, 총 판매 인원 수를 구한다.

달걀이 총 N개 밖에 없기 때문에

총 판매 인원수가 N보다 크다면 해당 인덱스의 값 * N 이 총 수입이 된다.

N 이하라면 해당 인덱스의 값 * (M - i) 가 총 수입이 된다.

이렇게 총 수입을 구해나가며 최대 수입을 갱신하고 갱신때마다 달걀 가격도 같이 갱신해준다.

탐색이 모두 끝났다면 답을 출력한다.

3-2. Python

import sys

N, M = map(int, sys.stdin.readline().split())

demands = []
revenue = 0
cost = 0

for i in range(M):
    P = int(sys.stdin.readline())
    demands.append(P)

demands.sort()

for i in range(M):
    total = N if M - i > N else M - i
    if revenue < demands[i] * total:
        revenue = demands[i] * total
        cost = demands[i]

print(cost, revenue)

3-3. C#

namespace boj_1246
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            int[] demands = new int[M];
            int revenue = 0;
            int cost = 0;

            for (int i = 0; i < M; i++)
                demands[i] = int.Parse(sr.ReadLine());

            Array.Sort(demands);

            for (int i = 0; i < M; i++)
            {
                int total;
                if (N < M - i)
                    total = N;

                else
                    total = M - i;

                if (revenue < demands[i] * total)
                {
                    revenue = demands[i] * total;
                    cost = demands[i];
                }
            }

            sw.WriteLine($"{cost} {revenue}");
            sw.Close();
        }
    }
}