문제

철수는 한양대학교 도서관에서 책을 빌려놓고 까먹고 있다가 며칠 후 책을 반납해야 한다는 사실을 깨달았다. 남은 기간 동안 최대한 많은 페이지를 읽고 연체없이 반납하고 싶다.

빌린 책은 여러 챕터로 구성된 에세이집인데 챕터들은 서로 독립적이다. 즉, 어느 챕터를 읽기 위해 다른 챕터를 먼저 읽어야 할 필요가 없다. 철수는 중간에 관두는 것을 못견디는 성격이라, 한 챕터를 읽기 시작하면 끝까지 봐야한다.

남은 기간 N일과, 책의 각 챕터 당 그 챕터를 전부 읽는데 소요되는 일 수와 페이지 수가 주어질 때, N일간 읽을 수 있는 최대 페이지 수를 구하는 프로그램을 작성하라.

입력

첫째 줄에 N(1 ≤ N ≤ 200)과 챕터의 수 M(1 ≤ M ≤ 20)이 주어진다. 둘째 줄부터 각 챕터 당 읽는데 소요되는 일 수와 페이지 수가 주어진다. 소요되는 일 수는 20보다 작거나 같은 자연수이고, 페이지 수는 300보다 작거나 같은 자연수이다.

출력

읽을 수 있는 최대 페이지 수를 출력한다.

예제 입력

7 7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

예제 출력

260

내가 했던 풀이 방법

배낭 문제 그 자체인 문제이므로, 배낭 문제 풀이 방법대로 풀이한다.

1. (M+1)×(N+1)의 배열을 0으로 채워준다.
2. 1부터 M까지 반복하면서 다음 연산을 진행한다. chapter[i-1]의 데이터를 date와 page에 저장해준다. (index는 1부터 시작하도록 구현했지만, chapter는 0부터 시작하므로 -1을 해주는 것에 유의한다.)
3. 1부터 N까지 j를 증가시켜준다. 이때, j는 현재 최대 일수를 의미한다. (배낭 문제는 최대가 1일때부터 N까지 dp 배열을 채워가면서 구한다.) 현재 최대 일수에서 date를 빼주었을 때 0보다 클 경우, dp[i - 1][j]와 dp[i - 1][j - date] + page중에 최댓값을 dp[i][j]에 저장한다. 0보다 작을 경우 dp[i - 1][j]을 저장해준다. (dp[i - 1][j]은 해당 챕터를 읽지 않았을 때의 최대 page이고, dp[i - 1][j - date] + page는 해당 챕터를 읽었을 때 최대 page가 된다. 즉, 이를 통해 해당 챕터를 읽을지 안읽을지를 결정해주게 된다.)
4. dp[M][N]에는 읽을 수 있는 최대 페이지 수가 저장되게 된다.

코드

const fs = require('fs');
let [n, ...chapter] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let N = Number(n.trim().split(' ')[0]);
let M = Number(n.trim().split(' ')[1]);

for (let i = 0; i < M; i++) {
  chapter[i] = chapter[i].trim().split(' ').map(Number);
}

let dp = Array.from({ length: M + 1 }, () => Array(N + 1).fill(0));

for (let i = 1; i <= M; i++) {
  let [date, page] = chapter[i - 1];
  for (let j = 1; j <= N; j++) {
    if (j - date >= 0) {
      dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - date] + page);
    } else dp[i][j] = dp[i - 1][j];
  }
}

console.log(dp[M][N]);

회고

배낭 문제 진짜 오랜만에 듣는 것 같다. 그래서 배낭 문제를 공부를 한 뒤에 풀이를 해서 쉽게 풀었다. 초반에 왜 저렇게 알고리즘이 나오는지 이해를 못해서 좀 오래 걸렸는데, 실제로 코드를 작성해보니까 왜 저렇게 해야하는지 감이 온 것 같다. 앞으로 이런 문제가 있으면 배낭 문제를 떠올리고 풀 수 있기 위해 기록한다.