백준 10738번 TETA

문제 링크입니다: https://www.acmicpc.net/problem/10738

세트에 포함된 어떠한 메뉴의 단품 가격보다 세트의 가격이 싸거나 같기 때문에 세트를 시킬 수 있는만큼 세트를 시킨 다음 나머지 메뉴를 시키도록 그리디(Greedy)하게 접근해야 하는 문제였습니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 20 + 1;

 

int price[MAX];

int meals[4];

int kindOfMeals[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int K;

        cin >> K;

 

        for (int i = 1; i <= K; i++)

                 cin >> price[i];

 

        int X;

        cin >> X;

 

        for (int i = 1; i <= 4; i++)

                 cin >> meals[i];

 

        int T;

        cin >> T;

 

        int sum = 0;

        for (int i = 0; i < T; i++)

        {

                 int num;

                 cin >> num;

 

                 kindOfMeals[num]++;

        }

 

        //세트를 시킬 수 있는만큼 시킨다

        while (kindOfMeals[meals[1]] + kindOfMeals[meals[2]] + kindOfMeals[meals[3]] + kindOfMeals[meals[4]] > 0)

        {

                 int temp = 0;

                 for (int i = 1; i <= 4; i++)

                         if (kindOfMeals[meals[i]])

                         {

                                 kindOfMeals[meals[i]]--;

                                 temp += price[meals[i]];

                         }

                 sum += min(X, temp);

        }

 

        //세트로 시키지 못한 음식 추가

        for (int i = 1; i <= K; i++)

                 sum += kindOfMeals[i] * price[i];

 

        cout << sum << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~