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

 

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

 

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

16493번: 최대 페이지 수

---

 

해결전략

 

Dynamic Programming 다이나믹 프로그래밍, 동적 계획법

배낭

 

 

---

 

코드

 

#include <iostream>
#include <vector>
using namespace std;

int n, m;//n 일수, m 챕터의 수
vector<int> day, chapter;
vector<vector<int>> dp;

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

	cin >> n >> m;

	day.resize(m+1);
	chapter.resize(m+1);
	for (int i = 1; i <= m; i++)
		cin >> day[i] >> chapter[i];

	//i개 이하의 챕터를 읽고, j일 이하를 지났을 때 읽을 수 있는 최대 페이지 수
	dp.resize(m+1, vector<int>(n+1, 0));
	for(int i=1; i<=m; i++){
		for(int j=1; j<=n; j++)
		{
			if (j >= day[i])
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-day[i]] + chapter[i]);
			else
				dp[i][j] = dp[i-1][j];
		}
	}
	
    //디버깅
	//for (int i = 1; i <= m; i++) {
	//	for (int j = 1; j <= n; j++) {
	//		cout << dp[i][j] << " ";
	//	}
	//	cout << "\n";
	//}
    
	cout << dp[m][n];

	return 0;
}

 

 

---