[PCCP 모의고사 #1] 체육대회

문제

문제 링크

당신이 다니는 학교는 매년 체육대회를 합니다. 체육대회는 여러 종목에 대해 각 반의 해당 종목 대표가 1명씩 나와 대결을 하며, 한 학생은 최대 한개의 종목 대표만 할 수 있습니다. 당신의 반에서도 한 종목당 1명의 대표를 뽑으려고 합니다. 학생들마다 각 종목에 대한 능력이 다르지만 이 능력은 수치화되어 있어 미리 알 수 있습니다. 당신의 반의 전략은 각 종목 대표의 해당 종목에 대한 능력치의 합을 최대화하는 것입니다.

다음은 당신의 반 학생이 5명이고, 종목의 개수가 3개이며, 각 종목에 대한 학생들의 능력치가 아래 표와 같을 때, 각 종목의 대표를 뽑는 예시입니다.

	테니스	탁구	수영
석환	40	10	10
영재	20	5	0
인용	30	30	30
정현	70	0	70
준모	100	100	100

테니스 대표로 준모, 탁구 대표로 인용, 수영 대표로 정현을 뽑는다면, 세 명의 각 종목에 대한 능력치의 합은 200(=100+30+70)이 됩니다.
하지만, 테니스 대표로 석환, 탁구 대표로 준모, 수영 대표로 정현을 뽑는다면 세 명의 각 종목에 대한 능력치 합은 210(=40+100+70)이 됩니다. 이 경우가 당신의 반의 각 종목 대표의 능력치 합이 최대가 되는 경우입니다.

당신의 반 학생들의 각 종목에 대한 능력치를 나타내는 2차원 정수 배열 ability가 주어졌을 때, 선발된 대표들의 해당 종목에 대한 능력치 합의 최대값을 return 하는 solution 함수를 완성하시오.

---

제한사항

• 1 ≤ ability의 행의 길이 = 학생 수 ≤ 10
• 1 ≤ ability의 열의 길이 = 종목 수 ≤ ability의 행의 길이
• 0 ≤ ability[i][j] ≤ 10,000
  • ability[i][j]는 i+1번 학생의 j+1번 종목에 대한 능력치를 의미합니다.

---

입출력 예

ability	result
[[40, 10, 10], [20, 5, 0], [30, 30, 30], [70, 0, 70], [100, 100, 100]]	210
[[20, 30], [30, 20], [20, 30]]	60

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 1번 학생이 2번 종목을, 2번 학생이 1번 종목의 대표로 참가하는 경우에 대표들의 해당 종목에 대한 능력치의 합이 최대가 되며, 이는 60입니다.

풀이

순열 문제로, nPr가지의 경우중 최대값을 구하는 문제다.(n=학생, r=종목)
문제에 주어진 조건상 최대 n이 10이라서 단순하게 DFS로 해결했지만 BigO가 팩토리얼인 문제라서 조금더 성능이 좋은 풀이를 찾아봤다.

한 정답자의 코드에서 bit연산을 통해 방문한 노드(이미 출전한 학생)를 체크해주는 방식을 보고 적용해봤다.

기존의 코드는 visited(value:출전한 학생들, i:출전한 종목) 배열을 만들어 재귀를 통해 조합을 구했다면, 수정한 코드는 출전한 학생들의 조합을 selected 변수에 담아 기록하고 출전한 종목을 num에 담아 기록한 방식이다.

selected 변수로 출전한 학생을 파악하는 방식은 111이면 차례로 첫째,둘째,셋째 학생이 출전 10110이면 두번째, 세번째, 다섯번째 학생이 출전했다는 의미다.
1부터 차례로 왼쪽으로 밀어주기 때문에 뒤에서부터 파악해야한다.

로직은 같지만 함수를 한번 호출할때 마다 배열을 수정하는 방식에서 비트연산으로 바꿔줬더니 최악의 경우 1.8s에서 최악의 경우 0.2s로 성능이 개선되었다.

코드

최종 코드(약 200ms)

function solution(ability) {
  let answer = 0;
  const dfs = (num, selected, score) => {
    if (num === ability[0].length) {
      if (answer < score) answer = score;
    } else {
      for (let i = 0; i < ability.length; i++) {
        if (!(selected & (1 << i)))
          dfs(num + 1, selected | (1 << i), score + ability[i][num]);
      }
    }
  };
  dfs(0, 0, 0);
  return answer;
}

정답을 참고하기 전 코드(약 1.8s)

function solution(ability) {
  let answer = 0;
  const dfs = (visited, score) => {
    if (visited.length === ability[0].length) {
      if (answer < score) answer = score;
    } else {
      for (let i = 0; i < ability.length; i++) {
        if (visited.indexOf(i) === -1)
          dfs([...visited, i], score + ability[i][visited.length]);
      }
    }
  };
  dfs([], 0);
  return answer;
}

참고한 코드(ENZYMATIC님)
정답 링크

function draft(ability, num, selected) {
  if (num >= ability[0].length) return 0;
  var maxScore = 0;
  for (var i = 0; i < ability.length; i++) {
    if (selected & (1 << i)) continue;
    maxScore = Math.max(
      maxScore,
      ability[i][num] + draft(ability, num + 1, selected | (1 << i))
    );
  }
  return maxScore;
}

function solution(ability) {
  return draft(ability, 0, 0);
}