(2024-10-28) 2 문제 : 백준 - 14718 (용감한 용사 진수)

 

 

병사의 수가 100개밖에 되지 않기 때문에 가능한 모든 조합을 구해도 시간초과가 발생하지 않는다.

단순하게 3중반복문을 통해 모든 힘, 민첩, 지능의 조합을 구한 뒤, 그 조합으로 이길 수 있는 병사의 수가 몇명이 되는지 개수를 세어 K를 넘는지 확인하면 된다. (K를 넘을 시, 합의 최소값을 갱신)

 

총 4중 반복문을 무식하게 돌려주면 되고, 최악의 경우에 1억번의 연산이 발생하지만 다행히 시간 초과는 발생하지 않는다.  

 

#include <iostream>
#include <vector>
#include <algorithm>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

struct Stat
{
    int Str = 0;
    int Dex = 0;
    int Int = 0;
};

std::vector<Stat> SoldierStats;

int main()
{
    Init();

    int NumSoldier = 0, NeedWin = 0;
    std::cin >> NumSoldier >> NeedWin;

    SoldierStats.resize(NumSoldier);

    for (int i = 0; i < NumSoldier; i++)
    {
        std::cin >> SoldierStats[i].Str >> SoldierStats[i].Dex >> SoldierStats[i].Int;
    }

    int Answer = 100000000;

    for (int i = 0; i < NumSoldier; i++)
    {
        for (int j = 0; j < NumSoldier; j++)
        {
            for (int k = 0; k < NumSoldier; k++)
            {
                int CurStr = SoldierStats[i].Str;
                int CurDex = SoldierStats[j].Dex;
                int CurInt = SoldierStats[k].Int;

                int Count = 0;

                for (int l = 0; l < NumSoldier; l++)
                {
                    if (SoldierStats[l].Str <= CurStr && SoldierStats[l].Dex <= CurDex && SoldierStats[l].Int <= CurInt)
                    {
                        Count++;
                    }

                    if (Count >= NeedWin)
                    {
                        Answer = std::min(Answer, CurStr + CurDex + CurInt);
                        break;
                    }
            	}
            }
        }
    }

    std::cout << Answer;

    return 0;
}