[백준 16493번] 최대 페이지 수 (C++)

문제링크 : https://www.acmicpc.net/problem/16493

16493번: 최대 페이지 수

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int day[21], page[21];
int dp[21][201];
int result = 0;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N, M;
    cin >> N >> M;
    for(int i=1; i<=M; i++) 
    {
        cin >> day[i] >> page[i]; 
    }

    for(int i=1; i<=M; i++)
    {
        for(int j=0; j<=N; j++)
        {
            if(j-day[i]>=0) dp[i][j] = max(dp[i-1][j], dp[i-1][j-day[i]]+page[i]);
            else dp[i][j] = dp[i-1][j];
        }   
    }

    cout << dp[M][N];

    return 0;
}

백준 1535번인 안녕 문제와 거의 동일한 DP 배낭 문제이다.

알고리즘 자체는 동일하나, 처음에 dp[M][N]이 아닌 dp[N][M]으로 작성하고 시간을 다소 낭비했던 문제이다.

 

주어진 요일 내에 최대한의 페이지를 읽는 것이 목적이므로 현재 주어진 일 수에 비교하여 최대 일 수인 N까지 읽을 수 있는 최대 페이지 수를 더해주면 된다.

 

dp[i][j] = i 챕터까지 j일 동안 읽을 수 있는 최대 페이지의 수