[백준 문제풀이] 16439번 치킨치킨치킨🍗 (node.js)

16439 치킨치킨치킨

문제

N명의 고리 회원들은 치킨을 주문하고자 합니다.

치킨은 총 M가지 종류가 있고 회원마다 특정 치킨의 선호도가 있습니다. 한 사람의 만족도는 시킨 치킨 중에서 선호도가 가장 큰 값으로 결정됩니다. 진수는 회원들의 만족도의 합이 최대가 되도록 치킨을 주문하고자 합니다.

시키는 치킨의 종류가 많아질수록 치킨을 튀기는 데에 걸리는 시간도 길어지기 때문에 최대 세 가지 종류의 치킨만 시키고자 합니다.

진수를 도와 가능한 만족도의 합의 최댓값을 구해주세요.

입력

첫 번째 줄에 고리 회원의 수 N (1 ≤ N ≤ 30) 과 치킨 종류의 수 M (3 ≤ M ≤ 30) 이 주어집니다.

두 번째 줄부터 N개의 줄에 각 회원의 치킨 선호도가 주어집니다.

i+1번째 줄에는 i번째 회원의 선호도 ai,1, ai,2, ..., ai,M (1 ≤ ai,j ≤ 9) 가 주어집니다.

출력

첫 번째 줄에 고리 회원들의 만족도의 합의 최댓값을 출력합니다.

예제 입력

3 5
1 2 3 4 5
5 4 3 2 1
1 2 3 2 1
--- 출력 13

4 6
1 2 3 4 5 6
6 5 4 3 2 1
3 2 7 9 2 5
4 5 6 3 2 1
--- 출력 25

문제 풀이

문제 이해부터가 어려웠던 문제🥲
처음에는 사람들의 선호도에서 max 값을 찾고 그 중에서도 높은 3개를 찾고 ... 이런 식으로 생각하다가 풀이가 말도 안돼서 다른 풀이를 참고했다.

전 문제인 카드 놓기 를 생각해 먹을 치킨의 조합을 구해놓고, 그 조합에 따른 사람들의 선호도 합계를 계산해서 최댓값을 구한다.

여기서 치킨의 조합을 고를 때에는, (0, 1, 2), (2, 1, 0) ... 이런 식으로 순서가 상관 없기 때문에 조합으로 생각하면 된다. m가지의 치킨 중 3가지의 치킨을 순서 상관 없이 뽑기!

n과 m(2) 문제처럼 치킨의 조합을 구할 수 있었다.

// 백준 16439번 치킨치킨치킨

const fs = require("fs");
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const [n, m] = input.shift().split(" ").map(Number);
const favor = [];

for (let i = 0; i < n; i++) {
  favor.push(input[i].split(" ").map(Number));
}

let visited = Array(m).fill(false);
let combination = [];
let result = 0;

// 3가지의 치킨 조합 만들기
const makeCombi = (start, num) => {
  if (num === 3) {
    let temp = makeSum(combination[0], combination[1], combination[2]);
    if (temp > result) result = temp;
    return;
  }
  for (let i = start; i < m; i++) {
    if (!visited[i]) {
      visited[i] = true;
      combination.push(i);
      makeCombi(i, num + 1);

      visited[i] = false;
      combination.pop();
    }
  }
};

const makeSum = (a, b, c) => {
  let sum = 0;
  for (let i = 0; i < n; i++) {
    sum += Math.max(favor[i][a], favor[i][b], favor[i][c]);
  }
  return sum;
};

makeCombi(0, 0);
console.log(result);

makeCombi 함수는 치킨의 조합을 구하는 함수이다. 3가지의 조합을 모두 구하면(depth가 3이 되면) 그 조합으로 사람들의 선호도를 계산한다.

makeSum 함수에서는 한 사람씩 for문을 돌면서 그 사람의 3가지 치킨의 선호도 중 가장 높은 값을 sum에 더하도록 한다.