백준 8903 장비

https://www.acmicpc.net/problem/8903

8903번: 장비

 

풀이 

0. 문제를풀기 앞서서 풀어야되는 문제

https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

개인적으로 비트마스킹을 공부하기 가장 좋았던 문제입니다.

 

 

1. 핵심 아이디어

 

K=2라고 생각해봅시다.

1,2,3번 능력치의 합이 최대인 장비를 A(1,2,3)

4,5번 능력치의 합이 최대인 장비를 B(4,5)라고하면

A(1,2,3)와 B(4,5)를 장착한 경우가 정답중 하나일 것입니다.

 

A(1,2,4)+B(3,5)인 경우도 마찬가지로 정답중 하나일 것이고.

A(2,3,5)+B(1,4), A(3,4)+B(1,2,5), A(1)+B(2,3,4,5)... 등 여러가지 경우가 존재합니다.

지금 예시는 K=2밖에 안되기 때문에 (2^5)^2의 경우의 수로 모두 고려 가능합니다.

이러한 경우의 수에 따른 값을 구하는 가정은 비트마스킹을 통해서 구현이 가능하고

입력에 따른 K에 따라서 나누는 갯수를 늘려주면됩니다.

 

문제에서는 K가 N까지 커지지만 5이상의 K는 의미 없습니다.

각 능력치별로 가장 큰 능력치를 가진 장비만 선택하면 끝이기 때문입니다. 따라서 K는 최대 5입니다.

때문에 (2^5)^5의 경우의 수로 브루트포스로 접근이 가능합니다.

코드

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

#define endl "\n"
#define int long long
#define float long double

const int INF = 999999999999999;
const int Dic[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

//////////////////////////////////////////////////////////////////////// 

int T, N, K;
struct Equip
{
	int r[5];
	Equip(int a, int b, int c, int d, int e)
	{
		r[0] = a;
		r[1] = b;
		r[2] = c;
		r[3] = d;
		r[4] = e;
	}
	int Get(int bit)
	{
		int result = 0;
		for (int i = 0; i < 5; i++)
			if (bit & (1 << i))
				result += r[i];
		return result;
	}
};
vector<Equip> Equips;
int BitValue[1 << 5];
int F(int bit, int deep)
{
	if (deep == K)
		return 0;

	int result = 0;
	for (int i = 1; i < (1 << 5); i++)
		if ((bit & i) == 0)
			result = max(result, BitValue[i] + F(bit | i, deep + 1));
	return result;
}

void Sol()
{
	for (int i = 1; i < (1 << 5); i++)
		BitValue[i] = 0;
	Equips.clear();

	std::cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		int a, b, c, d, e;
		std::cin >> a >> b >> c >> d >> e;
		Equips.emplace_back(a, b, c, d, e);
		for (int j = 1; j < (1 << 5); j++)
			BitValue[j] = max(BitValue[j], Equips[i].Get(j));
	}

	std::cout << F(0, 0) << endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> T;
	while (T--)
		Sol();
}