[platinum3] [풀이,분류 미확인]boj8903 장비

 

이 문제는 플레 3치곤 생각보다 쉬웠다. 비트마스킹 + 브루트포스로 접근이 가능하기도 하고 (최대 열크기가 5이하이기 때문)

그리디하게 K에 따라 항목별로 무엇을 택할지 정하면 되기 때문이다.

우선 K = 5일때 생각해보자.

4 2
30 30 30 30 0
50 0 0 0 0
0 50 0 50 10
0 0 50 0 20

다음과 같은 경우   1열 ~5열까지 돌면서 그대의 최댓값일때의 행의 장비를 선택하면 된다. 

만약 1열, 4열이 둘다 그 열에서 최댓값이면? 개의치 않아도 된다. 2열, 4열 이 최댓값이라, 1,3,5열에서 각각 장비를 하나씩 선택하면 장비를 4개 선택했는데, 이때가 최대이므로, 나머지 한개는 아무거나 선택하면 된다.

그럼 K > 5 일 경우엔? K= 5일때도 최댓값을 선택할 수 있는데 K > 5 일땐 고민할 필요도 없이 각열마다 최댓값을 뽑으면 된다.

아래와 같은 경우이다.

 

그럼이제 K = 4일때는 어떻게 해야 할까? 여기선 문제가 좀 있다. 4개만 뽑을 수 있으므로, 일단 장비3개는 각열마다 최댓값을 뽑을 수 있는데 , 나머지 1개는 어떻게 해야 할까?  바로 2개열의 합의 최댓값을 구하는 것이다. 다음과 같이 3,4,5열을 각 한열의 최댓값을 뽑았을 경우, 나머지 1열,2열의 합의 최댓값을 뽑아야 한다.  즉 5C3(5개중 3개열 선택) 해서 이때는 한개의 열의 최댓값, 나머지 열은 두개의 열 합의 최댓값 을 구하면 된다.  즉 완전탐색으로 구하는 것이다.

 

 

그러면 K = 3일때는?  이때는 조건이 좀 많아진다.

(2,2,1)  :   열2개 합 Max + 열2개합Max + 열1개합Max -> 5C2 * 3C2 1C1 / 2! : 

(3,1,1)    -> 5C3 * 2C1 * 1C1 / 2!

 

이런식으로 구하면 된다.

 

 

그럼 우선 할 일은 모든 경우의 수 즉 00000 , 00001 , 00010 , 00011  ... 11111 모든 경우의 수에 대한 열의 합의 값을 만드는 것이다. 즉 O(2^5  * 10000 ) 이 될 것이다. 위의 경우  bitMax[10001] = 50, bitMax[01010] = 100

(백트래킹으로 구한다)

 

또한 이제 K 일때  1~K까지 의 5자리 비트에 대해 합이 11111이 되도록 하는 모든 경우의 수를 구한다.

예시로 K = 2 이면, b[0] = 10111 b[1] = 01000 or b[0] = 10000 b[1] = 011111 이런 식으로 말이다.

이것또한 백트래킹으로 구했다. 그 뒤, B1, B2 , ... Bk 의 비트들에 대해  bitMax[Bk] 의 값들의 총합을 구하고 이값의  총합이 답이다.

 

유일한 자바 정답자!!