백준 16493 c++

현대 오토에버 코딩테스트에서 어려웠던 냅색 문제에 대해서 공부를 시작하겠다.
DP문제도 같이 공부할 수 있을 거 같다.

참고 :
https://velog.io/@pjh612/%EB%B0%B1%EC%A4%80-16493%EB%B2%88-%EC%B5%9C%EB%8C%80-%ED%8E%98%EC%9D%B4%EC%A7%80-%EC%88%98-cnilqgoz
https://yuu5666.tistory.com/20

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void input_chapter(int *N, int *M, vector<pair<int, int>> &chapter)
{
	int i, date, page;

	cin >> *N >> *M;
	chapter.push_back({ 0, 0 });
	for (i = 0; i < *M; i++)
	{
		cin >> date >> page;
		chapter.push_back({ date, page });
	}

	return;
}

void find_answer(int N, int M, vector<pair<int, int>>& chapter)
{
	vector<vector<int>> dp(M + 1, vector<int>(N + 1, 0));
	int i, j;

	//N : 남은 기간 : 가방의 최대 무게?
	//M : 챕터 수 : 물건 개수
	for (i = 1; i <= M; i++)
	{
		for (j = 1; j <= N; j++)
		{
			if (j >= chapter[i].first)//챕터를 새로 읽을 수 있는지?
			{
				dp[i][j] = max(dp[i-1][j], dp[i-1][j - chapter[i].first] + chapter[i].second);
			}
			else//없으면
			{
				dp[i][j] = max(dp[i][j], dp[i-1][j]);
			}
			//cout << dp[i][j] << " ";
		}
		//cout << "\n";
	}
	cout << dp[M][N] << "\n";

	return;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	vector<pair<int, int>> chapter;

	input_chapter(&N, &M, chapter);
	find_answer(N, M, chapter);

	return 0;
}