취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16493번 문제인 최대 페이지 수이다.
문제는 아래 링크를 확인하자.

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

챕터의 수 \(M\)이 많아야 20이므로, 읽을 챕터를 고르는 경우의 수는 \(2^{20}=1048576\)가지뿐임을 관찰하자. (읽는 순서에 상관없이 읽는 데에 드는 시간과 읽은 페이지수는 변하지 않음을 확인하자.)

따라서 모든 챕터 선택의 경우를 한번씩 살피는 완전 탐색을 통해 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int D, N;
int A[20], P[20];
int days, val, ans;

void func(int idx) {
    if (idx == N) {
        if (days <= D) ans = max(ans, val);
        return;
    }
    func(idx + 1);
    days += A[idx];
    val += P[idx];
    func(idx + 1);
    days -= A[idx];
    val -= P[idx];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> D >> N;
    for (int i = 0; i < N; i++) cin >> A[i] >> P[i];
    func(0);

    cout << ans;
}