[백준 - C#] 1246번 온라인 판매

문제링크

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

1246번: 온라인 판매

 

문제

경래는 닭을 기르는데 올 겨울 달걀 풍년으로 함박 웃음을 짓고 있다.
그리고 이 달걀을 영양란으로 둔갑하여 옥션에 판매하려한다.

경래는 총 N개의 달걀이 있고, 그의 잠재적인 고객은 총 M명이다.
그리고 각각의 i번째 고객은 각자 달걀 하나를 Pi 가격 이하로 살 수 있다고 밝혔다.

경래는 영양란이라 속인 죄책감에 한 고객에게 두 개 이상의 달걀은 팔지 않기로 하였다.
하지만 위의 규칙 하에 수익은 최대로 올리고 싶기에 얼마로 팔지 고민하고 있다.
즉, A가격에 달걀을 판다고 하면 Pi가 A가격보다 크거나 같은 모든 고객은 달걀을 산다는 뜻이다.
(물론 달걀 총 수량을 초과하여 팔 수 는 없다)

문제는 이러한 경래를 도와 최대 수익을 올릴 수 있는 달걀의 가장 낮은 가격을 책정하는 것이다.

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

첫째 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 입력된다.
둘째 줄부터 M+1번째 줄까지 i+1번째 줄에는 Pi(1 ≤ Pi ≤ 1,000,000)가 입력된다.

출력

첫째 줄에 경래가 책정한 가격과 이 가격으로 올릴 수 있는 수익을 출력한다.

 

문제정리

1. 달걀 가격이 정해지면 가격보다 큰 가격을 부른 고객은 살 수 있다.
2. 달걀의 총량보다 많이는 살 수 없다.
3. 최대 수익을 구할 수 있는 달걀의 최저 가격을 구해야합니다.

이번 문제의 경우 달걀의 갯수와 달걀을 구매해야되는 사람과 가격이 주어지면 달걀의 최저 가격으로 최대 수익을 낼 수 있는 수를 찾는 문제입니다.

달걀의 최저 가격을 구해야 하기 때문에 고객이 살 수 있는 금액을 오름차순으로 정렬하고 제일 작은 금액부터 차근차근 총 수익을 계산하여 max 값을 찾아내도록 그리디 알고리즘 방식으로 풀이를 진행하였습니다.

 

max값을 찾아내는 반복문을 진행 할 때 주의할점으로는 달걀을 사겠다는 사람보다 사람이 더 많을 경우가 있습니다.

그래서 예외처리를 해야합니다.

if ( M - i < N )  => 사람 수와 달걀의 갯수 비교
  P[i] * (M - i)  // 사람의 수보다 달걀의 갯수가 많을 때
else
  P[i] * N // 사람의 수가 달걀의 갯수보다 많을 때 사람의 수를 달걀의 갯수 만큼 구매

예외 처리를 하고나면 max값을 구하는 부분이니 나머지는 코드를 보며 확인해보시면 좋을 것 같습니다.

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    int N = int.Parse(input[0]);
    int M = int.Parse(input[1]);
    int[] P = new int[M];
 
    for (int i = 0; i < M; i++)
    {
        P[i] = int.Parse(reader.ReadLine());
    }
 
    Array.Sort(P); // 오름차순으로 정렬
 
    int temp;
    int price = 0;
    int max = 0;
 
    for (int i = 0; i < M; i++)
    {
        // 작은 수부터 순차적으로 계산
        // 달걀을 사겠다는 사람이 많다면 = P[i] * N
        // 달걀을 사겠다는 사람이 더더 적으면 = P[i] * (M - i)
        temp = (M - i < N) ? P[i] * (M - i) : P[i] * N;
 
        if (max < temp)
        {
            price = P[i];
            max = temp;
        }
    }
 
    writer.WriteLine($"{price} {max}");
 
    writer.Close();
    reader.Close();
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.