[BOJ] 8903번: Equipment

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

K >= 5이면 그냥 각 속성의 최댓값의 합으로 보아도 무방함을 쉽게 알 수 있습니다. 이제 K <= 4일 때가 문제인데, 직접 N Combination K를 처리하면 무조건 시간초과가 발생할 것입니다. 대신 아래와 같이 생각하면 효율적으로 풀 수 있습니다.

K = 2을 예로 들어보면, 최종적으로 얻은 답은 속성 1의 값이 한 장비에서 오고, 속성 (2,3,4,5)의 값이 다른 장비에서 왔거나

속성 2의 값이 한 장비에서 오고, 속성 (1,3,4,5)의 값이 다른 장비에서 왔거나

속성 (1,3)의 값이 한 장비에서 오고, 속성 (2,4,5)의 값이 다른 장비에서 왔거나

.

.

이런식으로 속성이 최대 2개의 그룹으로 나누어 각기 다른 장비에서 왔을 것입니다. 즉 (1,2,3,4,5)를 K개의 그룹으로 쪼개어 각각의 최댓값을 구한 후 더하면 됩니다. bitmasking을 이용해 코딩했습니다.

https://github.com/blisstoner/BOJ/blob/master/8903.cpp