[JavaScript/DP] 백준 골드 4 : 1633 - 최고의 팀 만들기

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

---

📌 작성한 코드 

// 1633
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = 15;
const len = input.length;

const white = [];
const black = [];

input.forEach((str) => {
    const [w, b] = str.split(" ").map(Number);
    white.push(w);
    black.push(b);
});

// dp[i][j][k] = i번째 선수일 때 백돌 j개, 흑돌 k개를 선택했을 때의 합
const dp = Array.from({ length: len }, () => Array.from({ length: N + 1 }, () => new Array(N + 1).fill(0)));

const solution = (i, wCount, bCount) => {
    if (wCount === N && bCount === N) return 0;
    if (i === len) return 0;

    if (wCount <= 15 && bCount <= 15 && dp[i][wCount][bCount]) return dp[i][wCount][bCount];

    let sum = solution(i + 1, wCount, bCount);
    if (wCount < N) sum = Math.max(sum, solution(i + 1, wCount + 1, bCount) + white[i]);
    if (bCount < N) sum = Math.max(sum, solution(i + 1, wCount, bCount + 1) + black[i]);

    dp[i][wCount][bCount] = sum;
    return sum;
};

console.log(solution(0, 0, 0));

 

📌 설명 

흑을 사용하는 플레이어 15명, 백을 사용하는 플레이어 15명을 선택해서 가장 높은 점수를 가지는 팀을 구하는 문제이다.

 

각 플레이어는 흑과, 백을 사용했을 때 얻을 수 있는 점수를 가지고 있다. 이 때 플레이어는 둘 중 하나만 선택해서 플레이 해야 한다.

또한 플레이어의 명수가 30 ~ 1000 사이의 값에서 주어지기 때문에 해당 플레이어를 선택할 수도 있고, 아닐 수도 있음을 고려해야 한다.

 

그렇다면 우리는 플레이어를 선택할 때 3가지를 확인해야 한다.

- 1. 몇번째 플레이어를 보고 있는지(i)

- 2. 현재까지 선택한 백 플레이어의 수(j)

- 3. 현재까지 선택한 흑 플레이어의 수(k)

 

이를 바탕으로 점화식을 세워 보면 이렇게 세울 수 있다.

점화식 : dp[i][j][k] = i번째 선수일 때 백 플레이어 j명, 흑 플레이어 k명을 선택했을 때의 최대값

 

dfs로 구현하고, dp를 사용해서 이미 구한 값은 바로 사용할 수 있도록 해주었다.

 

플레이어를 확인할 때 우리가 할 수 있는 행동은 3가지가 존재한다.

- 1. 현재 플레이어를 선택하지 않기 (백 플레이어와 흑 플레이어의 명수를 증가시키지 않고, 인덱스만 증가시키기) 

- 2. 현재 플레이어를 백 플레이어로 선택하기 (단, 백 플레이어가 15명을 넘지 않았을 경우)

- 3. 현재 플레이어를 흑 플레이어로 선택하기 (단, 흑 플레이어가 15명을 넘지 않았을 경우)

-> 해당 3가지 경우의 수에서 가장 큰 값을 dp에 저장한다.

 

 

✅ 성공