백준/ Silver 4 문제 , 백준 Node.js 자바스크립트 16439 치킨치킨치킨 [완전탐색]

백준/ Silver 4 문제 , 백준 Node.js 자바스크립트 16439 치킨치킨치킨  [완전탐색]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

 

문제 출처 🏠

 

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

16439번: 치킨치킨치킨

 

 

 

문제풀이 소감 🧑‍💻

문제가 약간 바로 이해되지 않았다. 3마리를 선택했을때의 최대 만족도라.....

근데 곰곰히 생각해보니 3마리를 구하면 각 사람마다 그 3마리에 대한 선호도들이 3개씩 있을거 아닌가?

그럼 그 3개중 선호도가 가장 큰 값이 그사람의 만족도 고 이런식으로 모든인원에서 구해서 합한 값이 가장 크면 된다.

 

 

요구사항 📋

N명의 회원이 가지고 있는 M개의 치킨 선호도들이 있다.

한사람의 만족도는 선택한 치킨들의 선호도 값들 중에서 가장 큰 값이다.

이 중 3마리의 치킨을 택했을 때 모든 회원의 만족도의 최댓값을 구하자.

 

주의 ❗

최대 3마리만 선택 가능하다.

 

해결 전략 📝

dfs 로 3개씩 선택해가면서 모든 만족도의 합을 비교해간다.

MAX 변수에 가장 큰 값을 저장해나아가자. 

 

 

 

 

정답 💯

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [input_N, input_M] = input[0].split(" ").map(Number);
input.shift();
const [...input_chickens] = input.map((v) => v.trim().split(" ").map(Number));

function solution(N, M, chickens) {
  const dfs = (idx) => {
    if (idx === 3) {
      let total = 0;
      for (let i = 0; i < N; i++) {
        total += Math.max(
          chickens[i][store[0]],
          chickens[i][store[1]],
          chickens[i][store[2]]
        );
      }
      if (MAX < total) MAX = total;
      return;
    }

    for (let i = 0; i < M; i++) {
      if (!visited[i]) {
        store.push(i);
        visited[i] = true;
        dfs(idx + 1);
        visited = false;
        store.pop();
      }
    }
  };
  let visited = Array.from({ length: N }).fill(false);
  let MAX = 0;
  let store = [];
  dfs(0);

  return MAX;
}

console.log(solution(input_N, input_M, input_chickens));