오늘은 pccp를 대비하여 모의고사를 풀어보았다.
그 중 2번 문제에 대해 기록을 남겨보고자 한다!!
1. 문제요약
학교가 체육 대회를 한다. 여러 종목에 대해 각 반의 대표자를 선정해야 한다.
- 하나의 종목에 대해 각 반의 대표 1명이 배정된다.
- 한 학생은 최대 한 개의 대표를 한다.
- 각 학생의 각 종목에 대한 능력치가 주어진다.
- 우리 반의 각 종목 대표자의 능력치 합을 최대화 해야 한다.
2. 제한사항
- 각 반의 인원수(즉 과목수)는 최대 10이다.
- 능력치의 최대값은 10,000이다.
3. 입출력
4. 알고리즘
제한 사항에서 최대 10명이다 라는 문구가 보이는가..?
바로 비트마스킹 문제이다!!
4.1 코드에서 사용될 비트마스킹 의미 알기
- 현재 학생 수(=과목 수)는 최대값인 10이라고 가정한다.
- 학생 번호는 0~9번까지이다.
[학생 선택 상태(mask)의 모든 경우의 수]
int maxMask = 1<<학생수
학생수의 최대값은 10이다. 즉 최악의 경우의 수가 고작 1024 밖에 안된다는 의미이다!
만약 학생 1과 3이 선택된다면, maxMask는 2진수로 0000001010, 10진수로는 10을 의미하게 된다.
[현재 학생 선택 상태 구하기]
for (int mask = 0; mask < maxMask; mask++) { ... }
우리는 위에서 전체 경우의 수는 1024개란 것을 안다.
그렇다면? 각 경우의 수를 for문으로 돌아가며 모든 경우의 수에 대한 학생들의 조합을 체크해줘야 한다.
[현재 선택된 학생 수(=현재 선택된 과목 수) 구하기]
[다음으로 선택해야 할 과목의 인덱스 구하기]
int task = Integer.bitCount(mask);
Integer.bitCount( )는 인자로 들어온 값을 2진수로 만들고, 1이 몇 개가 있는지 카운팅 해주는 함수이다!
위에서 예시를 든 10이 현재 mask 값이라면, 0000001010이 이진수 값이 되어 task 값이 총 2라고 나올 것이다.
하지만 인덱스는 현재값 -1 이기에, task라는 값은 바로 다음 선택될 과목의 인덱스를 의미하게 된다.
[다음으로 선택되어야 할 과목에 배정될 학생 찾기]
for (int i = 0; i < s; i++) { //학생 수 만큼 반복 if ((mask & (1 << i)) == 0) { // i 학생이 배정이 되지 않았다면, 해당 학생 배정시킴 int nextMask = mask | (1 << i); ... } }
현재 학생 수만큼 for문을 돌며, 현재까지 배정된 조합에서 해당 학생 자리 비트가 1이 아닐 시, 1로 만들어 준다.
[다음으로 선택되어야 할 과목 최대 값 찾기]
for (int i = 0; i < s; i++) { if ((mask & (1 << i)) == 0) { int nextMask = mask | (1 << i); dp[nextMask] = Math.max( dp[nextMask], dp[mask] + ability[i][task] ); } }
이제 우리는 다음과 같은 정보를 안다.
- 현재까지 선택된 학생들의 조합 (mask)
- 다음 선택되어야 할 과목 인덱스 (task)
- 다음 선택되어야 할 과목에 대한 학생들의 조합 (nextMask)
이젠 해당 학생들의 조합이 가질 수 있는 최댓값을 구해, dp를 갱신해주면 된다!!!
그 후 최종 정답은, 갱신된 dp 배열을 모두 돌며 가장 최댓값을 찾아주면 된다.
5. 최종 코드
import java.util.*;
class Solution {
public int solution(int[][] ability) {
int s = ability.length; // 학생 수
int m = ability[0].length; // 종목 수
int maxMask = 1 << s;
int[] dp = new int[maxMask];
for (int mask = 0; mask < maxMask; mask++) {
int task = Integer.bitCount(mask);
if (task >= m) continue; // 종목 끝
for (int i = 0; i < s; i++) {
if ((mask & (1 << i)) == 0) {
int nextMask = mask | (1 << i);
dp[nextMask] = Math.max(
dp[nextMask],
dp[mask] + ability[i][task]
);
}
}
}
int answer = 0;
for (int v : dp) answer = Math.max(answer, v);
return answer;
}
}
어려웠다.
