[알고리즘/백준/16439] 치킨치킨치킨(Nodejs, 완전탐색)

문제

---

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

16439번: 치킨치킨치킨

 

풀이

---

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [n, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, M] = n.split(" ").map(Number);
const pref = arr.map((row) => row.split(" ").map(Number));
let answer = Number.MIN_SAFE_INTEGER;

for (let i = 0; i < M; i++) {
  for (let j = 0; j < M; j++) {
    if (i === j) continue;
    for (let k = 0; k < M; k++) {
      if (i === k || j === k) continue;
      // 치킨 세 개 선택했을 때 각 학생 돌면서 최댓값 더하기
      let sum = 0;
      for (let l = 0; l < N; l++) {
        sum += Math.max(pref[l][i], pref[l][j], pref[l][k]);
      }
      answer = Math.max(sum, answer);
    }
  }
}

console.log(answer);

M 종류의 치킨 가운데 3가지를 선택할 때 만족도의 합이 최대가 되도록 치킨을 주문해야 한다. 한 사람의 만족도는 시킨 치킨 중에 선호도가 가장 큰 값이다. 

 

따라서 시킬 치킨을 3개 선택하고 해당 치킨에 대한 각 사람의 선호도를 구한다. 모든 사람의 선호도를 sum에 더했을 때 만족도 합의 최댓값을 answer에 저장한다.