[BOJ] 16493 최대 페이지 수

문제

16493번: 최대 페이지 수

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

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

풀이

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;

pii arr[200];
int n, m;
int dp[20][201];

int go(int chap, int d) {
    if (chap == m) {
        if (d > n) return -1e9;
        return 0;
    }
    if (d > n) return -1e9;
    if (dp[chap][d] != -1) return dp[chap][d];
    int ret = 0;
    ret += max(go(chap+1, d+arr[chap].first) + arr[chap].second, go(chap+1, d));
    return dp[chap][d] = ret;
}

int main() {
    memset(dp, -1, sizeof(dp));
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
    }
    printf("%d", go(0, 0));
}