[BOJ C++] 백준 16493번: 최대 페이지 수

 📚 문제

[BOJ C++] 백준 16493번: 최대 페이지 수
https://www.acmicpc.net/problem/16493

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• 이 문제는 배낭 문제와 같은 방법으로 해결할 수 있다. 즉, dp(dynamic programming)를 이용하여 해결하면 된다.
• d는 각 챕터를 읽는데 소요되는 일 수이고, p는 각 챕터의 페이지 수를 의미한다.
• dp[i][j]는 i번째 챕터까지 고려했을 때 j(1~n)일 동안 읽을 수 있는 최대 페이지 수를 의미한다. i-1번째 챕터까지 고려했을 때 j일 동안 읽을 수 있는 최대 페이지 수와 i-1번째 챕터까지 고려했을 때 j-d일 동안 읽을 수 있는 최대 페이지 수에 p를 더한 값 중, 더 큰 값을 선택하여 저장한다. 즉, 첫번째 경우는 i번째 챕터를 읽지 않는 경우, 두번째 경우는 i번째 챕터를 읽는 경우를 의미한다.
• [이론] 배낭 문제
  위 글에서 배낭 문제의 기본 개념, 점화식, 의사코드를 설명하고 있다.

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> dp(m+1, vector<int>(n + 1));
    for (int i = 1; i <= m; i++) { // i번 챕터.
        int d, p;
        cin >> d >> p;
        for (int j = 1; j <= n; j++) { // j일간 읽을 수 있는 최대 페이지 수. j: 1~n
            dp[i][j] = dp[i - 1][j];
            if (d <= j) dp[i][j] = max(dp[i][j], dp[i - 1][j - d] + p);
        } }

    cout << dp[m][n];
}