[Condingame] THE GIFT(돈을 나누는 가장 공평한 방식-탐욕 알고리즘)

문제 간략 설명: 이 게임의 등장인물은 영국 BBC 드라마 <닥터 후>에 나오는 외계종족 우드(Ood)와 해결사 역할을 하는 닥터입니다. 닥터는 타임머신 우주선을 타고 우드 행성에 착륙했습니다. 성년에 이른 한 우드를 위해 여러 우드들이 멋진 선물을 사주고 싶어 하지만, 각자 예산이 달라서 문제입니다.

[사진]

[Rules_규칙]

목표:

선물을 사려하는데 우드마다 가진 예산이 다릅니다.

최대한 공평하게 비용을 지출해야 하는 상황입니다.

프로그램은 사람이 선물을 살 충분한 돈이 있는지 확인하고, 각자 지출해야 할 금액을 계산해야 합니다.

 

규칙: 

닥터는 우드의 개별 예산 리스트를 가지고 있고, 최대한 개인의 지출 비용을 비슷하게 책정하
려 합니다. 최적의 해결책을 찾기 위해 닥터는 다음과 같이 기준을 정했습니다.
모두 자신의 예산 내에서만 지출할 수 있으며, 각자의 지출 비용은 다를 수 있습니다. 우
드 중 어느 누구도 본인의 가진 금액을 초과해서 지출할 수 없습니다.

1. 가장 많은 비용을 내는 우드의 지출액을 최소한으로 합니다.
2. 위 조건을 만족하는 최적의 방법이 여러 가지일 경우 두 번째로 많은 비용을 내는 우드의
지출액을 최소화하는 방법을 택하고, 그래도 같은 방법이 여러 가지라면 다음 순서로 많
은 비용을 내는 우드의 지출액을 최소화합니다. 다시 말해 모든 우드가 최대한 서로 비슷
한 액수의 비용을 지출하는 방법을 찾아야 합니다.

3. 계산의 편의를 위해 모든 금액은 정수형으로만 지출합니다.

 

[문제]

 

https://www.codingame.com/training/medium/the-gift

Practice Greedy algorithms with the exercise "The Gift"

 

[난이도]

[학습 개념]

[풀이]

문제를 푸는 것보다 문제 파악이 더 어려울 때가 있습니다. 이 문제가 저에겐 그랬습니다.

예제 3번째를 보면 입력이 100, 1, 60으로 받는데 지출은 1, 49, 50을 지출하는 걸 볼 수 있습니다.

처음에는 100을 낸 사람이 1을 내고, 1을 낸 사람이 49를 내고, 60을 낸 사람이 50을 내는 줄 알았습니다.

정말 왜 이러나.. 규칙을 봐도 더 이해가 안 가고.. 정말 이해가 안 갔습니다.

이해가 정말 안 가서 문제를 다시 꼼꼼히 읽었습니다.

그러더니 보이더군요 OutPut 조건에 금액 리스트를 오름차순으로 하라는 말이 있었습니다.

ㅠㅠ 문제 꼼꼼히 읽어야 된다고 문제한테 매 맞는 느낌이네요 o(><；) oo

그리니 이해 됬습니다 1, 60, 100 순으로 금액을 오름차순으로 정렬하고 1은 너무 적은 금액으로 그냥 받고 남은 선물 금액에서 둘이 평균을 내서 60낸 얘가 49를 내고 그 나머지 금액을 가장 많이 낸 사람이 다 낸다는 걸요

 

이렇게 문제를 이해하니 코드 짜는 건 쉬었습니다.

 

[소스 코드]

 

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
class Solution
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine()); // 선물 구매에 동참하는 사람 수
        int C = int.Parse(Console.ReadLine()); // 선물 가격
        int[] Budgets = new int[N]; // 예산을 담을 배열

        int totalBudget = 0;

        for (int i = 0; i < N; i++)
        {
            Budgets[i] = int.Parse(Console.ReadLine()); //각각의 예산
            totalBudget += Budgets[i];
        }

        //예산의 합이 선물 가격보다 적으면
        if (totalBudget < C)
        {
            Console.WriteLine("IMPOSSIBLE");
            return;
        }

        //가장 예산이 적은 사람부터 차례대로 확인해야 가장 공평하게 선물 가격을 지불함
        Array.Sort(Budgets);

        //예산의 합이 선물 가격보다 크면 계속 진행
        for (int i = 0; i < Budgets.Length; i++)
        {
            // 각각의 사람이 내야할 선물의 평균 값
            // 평균은 계속 업데이트 해줘야함
            int averageCost = C / N;

            //만약 평균 값보다 예산이 적다면
            if (Budgets[i] < averageCost)
            {
                Console.WriteLine(Budgets[i]);
                C -= Budgets[i]; // 예산 전체를 낸다
            }
            else
            {
                Console.WriteLine(averageCost);
                C -= averageCost;//예산에서 평균값만 내기
            }
            //낸 사람은 제외한다.
            N--;
        }
    }
}

 

[아쉬웠던 점]

다 하고 나니 코드를 더 똑똑한 방법으로 짤 수 있었다는 걸 다른 분들의 코드를 보고 깨달았습니다.

구현하는데만 신경 써서 아는 기능도 안 썼던 점이 아쉽습니다.

밑의 코드는 Linq 네임스페이스에서 제공하는 Sum(), Min()을 쓴 코드입니다.

훨씬 깔끔합니다.

 

using System;
using System.Linq;

class Solution
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int C = int.Parse(Console.ReadLine());
        int[] Budgets = new int[N];

        for (int i = 0; i < N; i++)
        {
            Budgets[i] = int.Parse(Console.ReadLine());
        }

        if (Budgets.Sum() < C)
        {
            Console.WriteLine("IMPOSSIBLE");
            return;
        }

        Array.Sort(Budgets);

        for (int i = 0; i < Budgets.Length; i++)
        {
            int fair = C / (Budgets.Length - i);
            int contribution = Math.Min(fair, Budgets[i]);
            Console.WriteLine(contribution);
            C -= contribution;
        }
    }
}

[새롭게 알게 된 점]

이 문제를 풀면서 탐욕 알고리즘을 사용해야 한다고 하는데 풀고 나서도 "내가 탐욕 알고리즘을 사용한 건가?"라는 의문을 가졌습니다. 그래서 공부해서 새롭게 알게 된 점을 공유하려고 합니다.

탐욕 알고리즘( greedy algorithm )

탐욕 알고리즘은 특별한 코드가 있는 알고리즘이 아닌 개념적인 알고리즘입니다. 어떠한 문제에도 적용할 수 있지만, 문제마다 적용하는 방식은 모두 다릅니다.

 

최적의 해 또는 근사해를 구하는 데 사용하는 방법으로, 문제를 여러
단계로 나누고 각 단계에서 최적의 수를 찾아낸 후 각 단계에서 판단한 최적의 수를 모아 문제의
최종 답을 찾는 알고리즘을 말합니다. 

 

탐욕 알고리즘은 모든 경우의 수를 계산하는 데 시간이 오래
걸리거나 방법이 복잡한 경우 간단한 방법으로 비교적 빠르게 최적의 결과 또는 최적에 근사한 결과를 얻을 수 있을 때 

주로 사용합니다.

 

모든 경우의 수를 확인하는 방법으로는 무차별 대입법 또는 브루트-포스(brute-force) 방법이라고 합니다. 무차별 대입법은 알고리즘이라고 불리기는 조금 민망하지만, 모든 경우의 수를 다 계산하여 일일이 확인하기 때문에
시간은 오래 걸려도 정답은 확실히 찾을 수 있다는 장점이 있습니다.

하지만 경우의 수가 많은 문제에 대해서는 시간이 매우 오래 걸릴 수 있습니다.

 

다시 돌아와서 탐욕 알고리즘은 적용 시 최선의 선택 기준을 어떻게 알아내느냐 하는 것입니다.

이를 단번에 알아내는 쉬운 방법은 없습니다.

 

제가 알아본 한 가지 팁은, 문제를 푸는 방법이 모든 경우의 수를 확인해야 하고, 또 그 경우의 수가 기하급수적으로 늘어나는 겨우라면 탐욕 알고리즘을 고려해 볼 만합니다.

최선의 선택 기준은 주어진 데이터에서 판단할 수 있는 항목을 모두 열거하고, 하나씩 제거하면서 확인하는 것이 한 가지 방법이 될 수 있습니다.

 

이 방법으로 푼 문제가 있습니다. 그 문제 풀이 블로그 글을 포스팅하고,  THE GIFT 문제 풀이를 더 설명하고 글을 마치겠습니다.

2023.05.11 - [분류 전체보기] - [Condingame] SUPER COMPUTER(가장 효율적인 스케쥴-탐욕 알고리즘)

[Condingame] SUPER COMPUTER(가장 효율적인 스케쥴-탐욕 알고리즘)

 

---

탐욕 알고리즘을 공부하면서 저는 어떤 생각으로 이 문제를 풀었나 생각을 해 보았습니다.

나는 어떤 기준을 정해 최선의 선택으로 문제를 푼 건지 고민해 보았습니다.

그렇게 풀이 과정을 보면서 생각해 보니 저는 가장 적은 예산을 낸 사람부터 평균을 기준으로 탐욕 알고리즘을 썼었습니다.

 

예산을 정렬하고 가장 적은 금액을 가진 친구부터 1명씩 평균액 또는 금액 전부를 지출하고, 지출한 금액만큼 선물 가격에서 차감한 후 남아 있는 인원으로 평균을 재계산한 후, 이 과정을 모든 친구가 금액을 지출할 때까지 반복했습니다.

 

즉, 이 문제는 정렬 한 예산 리스트를 평균을 기준으로 푸는 탐욕 알고리즘이었다는 걸 새롭게 알게 되었습니다.