문제 풀이

dp[i][j]로 i챕터까지 j일이 남았을 때 읽을 수 있는 최대 페이지 수로 정의한다.

이중 for문을 사용해서 i챕터를 읽을 경우와 읽지 않을 경우를 모두 확인한다.

i챕터를 읽을 경우에는 i-1 챕터까지 확인한 결과 중 j-arr[i][0]일을 사용해서 읽은 최대 페이지 수 + i챕터의 페이지 수(dp[i-1]j-arr[i][0]] + arr[i][1])
와 이전 챕터까지 확인 했을 경우의 최대 페이지 수(dp[i-1][j]) 중 최대값을 고르고

i챕터를 읽지 않은경우에는 dp[i-1][j]와 dp[i][j]를 비교 해서 최대값을 고른다.

그렇게 하면 정답은 dp[m][n]에 있게 된다.

문제 링크

boj/16493

소스코드

PS/16493.cpp

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
#include<map>
#include<queue>
using namespace std;

int dp[21][201];
int arr[21][2];
int main(void)
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> arr[i][0]>>arr[i][1];
	}
	for (int i = 1; i <= m; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			if (j - arr[i][0] >= 0)
				dp[i][j] = max(dp[i - 1][j - arr[i][0]] + arr[i][1],dp[i - 1][j]);
			dp[i][j] = max(dp[i - 1][j], dp[i][j]);
		}
	}
	cout << dp[m][n];
}