백준 8903 장비 - C++

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

8903번: 장비

신촌 알고리즘 중급반 연습문제.. 고민을 거듭하다가 결국 모르겠어서 구글에 검색해서 다른 사람의 풀이를 보고 접근했다.

 

<문제>

 

문제가 너무 길어서 간단히 요약하면, 5개 부문에서 각각 별개의 능력치를 모두 지닌 장비들이 입력으로 주어지고, 입력으로 주어진 K의 개수만큼 착용할 수 있다. 또, 장비를 여러 개 착용하면 장비들의 능력치가 합연산으로 적용되는 게 아니라,  각 능력치마다 착용한 장비 중에서 가장 높은 능력치만 적용된다. 예를 들어 1번 능력치가 10, 15인 장비를 2개 착용하면, 15만 적용된다는 이야기이다.

 

이런 조건들에서 가능한 가장 높은 능력치 총합을 출력하는게 목표이다. 

 

 <입력>

 

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N과 K가 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ K ≤ N) 다음 N개 줄에는 0보다 크거나 같고, 10,000보다 작거나 같은 정수 다섯 개가 주어지며, 이 정수는 각 장비의 점수 ri,1, ri,2, ri,3, ri,4, ri,5를 나타낸다. 인접한 두 정수 사이에는 빈 칸이 하나 있다.

 

<출력>

 

각 테스트 케이스 마다, 장비 N개중 K개를 착용했을 때, 가장 큰 향상 점수의 합을 출력한다.

 

<접근 방식>

 

일단 K가 5보다 크거나 같으면, 자명하게 각 능력치마다 제일 큰 장비들을 고르면 된다.

 

문제는 K가 5보다 작은 경우인데, 

 

K =1인 경우에는, 간단하게 총합 능력치가 가장 큰 장비를 착용하면 되겠지만,

K=2, 3, 4의 경우에는? 위의 조건들과 비슷하게 접근하면 굉장히 많은 예외들이 있다.

 

여기서 주목할 것은 결국 능력치는 5개로 고정되어 있고, 우리가 고려해야 하는 K의 크기 역시 4 이하의 자연수라는 것이다.

 

5개의 능력치를 K개의 그룹에 분배하고, 그 모든 경우에 대한 최대값을 구하는 건 시간이 얼마나 걸릴까?

 

말은 어렵지만 K=2인 경우, 각 장비에서 챙길 능력치들을 [1]. [2, 3, 4, 5] 또는 [2] [1, 3, 4, 5] ... 5C2 꼴로 5개의 능력치를 2개의 그룹에 분배해주면 모든 경우를 고려할 수 있다.

 

다행히 K와 능력치의 개수가 작기 때문에 O(k^5 * N)의 시간 복잡도를 가지는 이 풀이는 적용가능하다.

 

자세한 내용은 아래 주석에.... 

 

P.S. 난이도가 일정 이상 올라가면, 오히려 수가 작아지는 경우에 있어서 이렇게 Brute Force 한 발상을 쓰는 경우가 많은 거 같다. 수상한 조건들을 잘 캐치하자.