[JavaScript] 백준 17845 수강 과목

수강 과목

📚 문제 설명

K개의 과목이 있고 N시간 동안 공부를 할 수 있다.
각각의 과목에는 중요도와 필요한 공부 시간이 있을 때, 최대의 중요도를 얻으며 공부를 할 수 있는 방법은 무엇인가.

공부를 절반하면 절반의 중요도를 얻는 것은 아니다.

👨🏻‍💻 풀이 과정

이 문제는 일반적인 배낭 문제처럼 풀면 된다. 따라서 배낭 문제를 풀 때 사용하는 2가지 방법으로 진행했다.

1. 2차원 배열을 활용하는 방법.
2. 1차원 배열을 활용하는 방법.

우선 두 방법 모두 N 길이 만큼의 배열을 이용하여 각각의 과목의 중요도 합의 최댓값을 저장한다는 점에서 동일하다.

배낭 문제의 상세한 설명은 이전 게시글을 참고하면 좋을 것 같다.

💡2차원 배열

2차원 배열 dp의 의미는 다음과 같다.

dp[?번째 과목을 포함][?시간 동안 공부] = 우선순위의 최댓값

그럼 예를 들어 dp[2][80]은 1~2번째 과목까지 중에 80시간을 공부했을 때의 최대 우선순위 값을 의미한다.

점화식의 대한 자세한 설명은 아까 말했던 이전 게시글을 참고

2차원 배열 이용 코드

let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");

const [N, K] = input.shift().split(' ').map(Number);
const todos = input.map(v => v.split(' ').map(Number));
const dp = Array.from({length: K + 1}, _ => Array(N + 1).fill(0));

for (let i = 1; i < K + 1; i++) {
    const [value, weight] = todos[i - 1];
    for (let j = 1; j < N + 1; j++) {
        if (j >= weight) {
            dp[i][j] = Math.max(dp[i - 1][j - weight] + value, dp[i - 1][j]);
        } else {
            dp[i][j] = dp[i - 1][j];
        }
    }
}
console.log(dp[K][N]);

💡1차원 배열

1차원 배열을 이용한 코드도 전체적인 맥락을 동일하다.
가장 핵심은
dp[i][j] = Math.max(dp[i - 1][j - 무게] + 가치, dp[i - 1][j])
이 것을 이해하면 1차원 배열에도 동일하게 적용이 가능하다는 것이다.

1차원 배열 이용 코드

let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");

const [N, K] = input.shift().split(' ').map(Number);
const todos = input.map(v => v.split(' ').map(Number));
const singleArr = Array(N + 1).fill(0);

for (const todo of todos) {
    const [value, weight] = todo;

    for (let i = N; i >= weight; i--) {
        singleArr[i] = Math.max(singleArr[i - weight] + value, singleArr[i]);
    }
}
console.log(singleArr[N]);

🧐 후기

오랜만에 배낭 문제를 접하니 조금 막막해서 이전에 풀었던 풀이를 확인하고 돌아왔다.