백준 8903번 장비

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

장비를 5개 이상 이용할 경우에는 그리디하게 접근하여 각 장비 당 최대 점수를 갖고 있는 장비를 5개 고르면 되지만, 장비가 1개 이상 4개 이하일 경우 위와 같은 그리디한 접근은 옳지 않은 것을 알 수 있습니다.

N이 최대 10,000이기 때문에 모든 경우를 그대로 완전탐색해버리면 TLE가 나는 까다로운 문제였습니다.

따라서, 각 장비를 K개의 그룹으로 나누어 해당 그룹에 속한 능력치들의 합이 최대인 장비를 고르는 쪽으로 접근하면 되는 문제였습니다.

*학회 슬랙을 통해 같은 학교 학우이신 Green55님이 많은 힌트를 주셨습니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 10000;

 

int N, K;

int result;

int ability[MAX][5];

vector<int> gadget[5];

 

//완전탐색 진행

void func(int idx)

{

        if (idx == 5)

        {

                 int temp = 0;

                 //i번 그룹에 속한 능력치들의 합이 최대인 장비를 고른다.

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

                 {

                         int maxAbility = 0;

                         for (int j = 0; j<N; j++)

                         {

                                 int sum = 0;

                                 for (int k=0; k<gadget[i].size(); k++)

                                          sum += ability[j][gadget[i][k]];

 

                                 maxAbility = max(maxAbility, sum);

                         }

 

                         temp += maxAbility;

                 }

 

                 result = max(result, temp);

                 return;

        }

 

        //K개의 그룹에 분배

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

        {

                 gadget[i].push_back(idx);

                 func(idx + 1);

                 gadget[i].pop_back();

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int T;

        cin >> T;

 

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

        {

                 cin >> N >> K;

 

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

                         for (int j = 0; j < 5; j++)

                                 cin >> ability[i][j];

 

                 result = 0;

                 if (K < 5)

                 {

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

                                 gadget[i].clear();

 

                         func(0);

                 }

                 //각 장비의 최대값을 구해주면 된다

                 else

                 {

                         vector<int> v(5, 0);

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

                                 for (int j = 0; j < 5; j++)

                                          v[j] = max(v[j], ability[i][j]);

 

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

                                 result += v[i];

                 }

                 cout << result << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

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