100. 최대점수 구하기(냅색 알고리즘) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★☆☆☆

#include <iostream>
#include <vector>

using namespace std;

struct Exam
{
	int score;
	int time;
	
	Exam(int x, int y)
	{
		this -> score = x;
		this -> time = y;
	}
};


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, a, b;
	
	cin >> n >> m;
	
	vector<Exam> V;
	vector<int> Scores(m+1, 0);
	
	V.push_back(Exam(0, 0));
	
	for(int i = 0; i < n; i++)
	{
		cin >> a >> b;
		V.push_back(Exam(a, b));
	}
	
	for(int i = 1; i <= n; i++)
	{
		Exam exam = V[i];
		for(int j = m; j >= 0; j--)
		{
			if(j - exam.time < 0) break;
			
			if(Scores[j - exam.time] + exam.score > Scores[j])
				Scores[j] = Scores[j - exam.time] + exam.score;
		}
	}
	
	cout << Scores[m] << "\n";
	
	return 0;
}

1. 동전교환처럼 개수가 무한이면 1차원 벡터의 앞에서부터, 이 문제처럼 문제의 개수가 1개(유한)이라면 1차원 벡터 뒤에서부터 진행하면 된다.