16493 최대 페이지 수

입력이 작아서 모든 경우의 수를 다 구해도 되겠다 싶었다. 

비트마스크로 모든 경우를 다 구해서 페이지 합산, 일 합산을 구한다.

일 합산이 기한보다 작은 경우 최대 페이지 수를 구한다. 끝~

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;


int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    vector<ii> v(m);
    for (int i = 0; i < v.size(); i++) {
        scanf("%d %d", &v[i].xx, &v[i].yy);
    }
    
    int ans = 0;
    for (int i = 0; i < (1 << m); i++) {
        int dateSum = 0;
        int pageSum = 0;
        for (int j = 0; j < m; j++) {
            if (i & (1 << j)) {
                dateSum += v[j].xx;
                pageSum += v[j].yy;
            }
        }
        if (dateSum <= n)
            ans = max(ans, pageSum);
    }
    
    printf("%d\n", ans);
    
    
    return 0;
}

 

현욱님 코드 넵섹

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int table[205][25];
vector<ii> book;

// day: 남은 일 수, idx: 인덱스
int solve(int day, int idx) {
    // book 사이즈 만큼만 확인
    if (idx == book.size())
        return 0;
    
    auto& res = table[day][idx];
    
    if (res != -1)
        return res;
    
    // 책을 안 읽는 경우
    res = solve(day, idx + 1);
    
    // 책을 읽는 경우
    // 소요되는 일 수가 현재 일 수보다 작다면
    if (book[idx].xx <= day)
        // 남은 일 수에서 소요되는 일 수를 뺸다
        // 그리고 챕터의 수는 더한다
        res = max(res, solve(day - book[idx].xx, idx + 1) + book[idx].yy);
    
    // 책을 읽는 경우 / 안 읽는 경우 중 큰 값 리턴
    return res;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    // dp 초기화를 합니다
    memset(table, -1, sizeof(table));
    
    book.resize(m);
    
    for (int i = 0; i < m; i++)
        scanf("%d %d", &book[i].xx, &book[i].yy);
    
    printf("%d\n", solve(n, 0));
    
    return 0;
}