[BOJ/Silver 2] 백준 16493 최대 페이지 수(C++)

문제 링크

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

16493번: 최대 페이지 수

 

문제

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

빌린 책은 여러 챕터로 구성된 에세이집인데 챕터들은 서로 독립적이다. 즉, 어느 챕터를 읽기 위해 다른 챕터를 먼저 읽어야 할 필요가 없다. 철수는 중간에 관두는 것을 못견디는 성격이라, 한 챕터를 읽기 시작하면 끝까지 봐야한다. 

남은 기간 N일과, 책의 각 챕터 당 그 챕터를 전부 읽는데 소요되는 일 수와 페이지 수가 주어질 때, N일간 읽을 수 있는 최대 페이지 수를 구하는 프로그램을 작성하라.

입력

첫째 줄에 N(1 ≤ N ≤ 200)과 챕터의 수 M(1 ≤ M ≤ 20)이 주어진다. 둘째 줄부터 각 챕터 당 읽는데 소요되는 일 수와 페이지 수가 주어진다. 소요되는 일 수는 20보다 작거나 같은 자연수이고, 페이지 수는 300보다 작거나 같은 자연수이다.

출력

읽을 수 있는 최대 페이지 수를 출력한다.

예제 입력 1

7 7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

예제 출력 1

260

예제 입력 2

5 3
2 100
2 20
2 40

예제 출력 2

140

알고리즘 분류

• 배낭 문제

풀이

냅색 알고리즘으로 해결할 수 있다.

DP[20][200]라는 2차원 배열을 선언하고, 여기에 i번째 챕터까지 읽고 j일이 걸렸을 때 몇 페이지를 읽었는지 기록한다.

다만, j는 N을 넘을 수 없다.

페이지 수를 기록해주면서 페이지 수의 최댓값을 구해준다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX_M 21
#define MAX_N 201
#define LL long long
#define INF 1e9

using namespace std;
int N, M;
int D[MAX_M], P[MAX_M];
int DP[MAX_M][MAX_N];
int Answer = 0;

void Input() {
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		cin >> D[i] >> P[i];
	}
}

void Settings() {
	for (int i = 1; i <= M; i++) {
		for (int j = N; j >= 0; j--) {
			if (j - D[i] >= 0) {
				DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - D[i]] + P[i]);
			}
			else {
				DP[i][j] = DP[i - 1][j];
			}
			Answer = max(Answer, DP[i][j]);
		}
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}