[백준] 14718번 : 용감한 용사 진수 (C++)

14718번 : 용감한 용사 진수

---

문제)

N명의 적 병사가 있다. 적의 각 병사는 힘, 민첩, 지능의 3가지 능력치를 가진다. 용감한 용사 진수도 힘, 민첩, 지능의 3가지 능력치를 가진다.

적의 각 병사에 대해,

1. 적 병사가 가진 힘보다 진수의 힘이 크거나 같고,
2. 적 병사가 가진 민첩보다 진수의 민첩이 크거나 같고,
3. 적 병사가 가진 지능보다 진수의 지능이 크거나 같으면,

진수는 그 적 병사를 이길 수 있다.

용감한 용사 진수에게 스탯 포인트를 주면 똑똑한 진수는 자기가 최대한 많은 적을 이길 수 있도록 스탯 포인트를 스스로 분배한다.

N명의 병사들 스탯이 주어졌을 때, 진수가 적어도 K명의 병사를 이길 수 있게 하는 최소의 스탯 포인트를 구하여라.

 

 

 

입력 :

첫 번째 줄에는 N명의 병사 수와 용감한 용사 진수가 이겨야 할 K명의 병사 수가 주어진다. (1 ≤ K ≤ N ≤ 100)

두 번째 줄부터 N+1 번째 줄까지 각 줄마다 병사들의 힘, 민첩, 지능을 세 개의 음이 아닌 정수로 주어진다. (0 ≤ 힘, 민첩, 지능 ≤ 1000000)

 

 

 

출력 :

용감한 용사 진수가 적어도 K명의 병사를 이길 수 있게 하는 최소의 스탯 포인트를 출력하여라.

 

 

 

 

 

풀이)

 

// 14718. 용감한 용사 진수
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
 
using namespace std;
 
int n, m;
vector<vector<int>> vec;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    int a, b, c;
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b >> c;
        vec.push_back(vector<int> {a, b, c});
    }
 
    int answer = INT_MAX;
 
    // 주어진 병사들을 기반으로 조합해
    // 진수의 스텟을 설정한다.
 
    // 3중 for문을 이용해서 스텟의 모든 조합을 확인
    
    // 모든 병사의 스텟 조합 / 100 * 100 * 100 -> 100만번
    // 해당 스텟 조합으로 적을 얼마나 이길 수 있는지 계산 100
    // 총 100000000 -> 1억번이므로, 1초내에 계산이 가능하다.
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                int cnt = 0;
 
                int _str = vec[i][0];
                int _dex = vec[j][1];
                int _int = vec[k][2];
 
                for (int l = 0; l < n; l++)
                {
                    if (vec[l][0] <= _str
                        && vec[l][1] <= _dex
                        && vec[l][2] <= _int)
                    {
                        cnt++;
                    }
                }
 
                if (cnt >= m)
                {
                    answer = min(answer, _str + _dex + _int);
                }
            }
        }
    }
    
    cout << answer;
 
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/14718 

14718번: 용감한 용사 진수