정답 코드 출처

#include <iostream>
#include <vector>

using namespace std;

int n = 0;
int m = 0;


int cost[101];
int bite[101];
int dp[101][10001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int sum_cost = 0;
	cin >> n >> m;

	//최대 비용은 비용은 정해져있음 이 비용중 가장 먼저 m에 과 똑같은 bite를 가진 비용울 출력하면됨

	for (int i = 1; i <= n; i++) {
		cin >> bite[i];
	}

	for (int i = 1; i <= n; i++) {
		cin >> cost[i];
		sum_cost += cost[i];
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= sum_cost; j++) {
			if (j - cost[i] >= 0) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j - cost[i]] + bite[i]);
			}
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
		}
	}

	for (int i = 0; i <= sum_cost; i++) {
		if (dp[n][i] >= m) {
			cout << i;
			break;
		}
	}
	

	return 0;
}

실패 코드

#include <iostream>
#include <vector>

using namespace std;
int n, m;

vector<int> memory;
vector<int> cost;

int result = 10000000;

vector<pair<int, int>> dp[10000000];

//dp 이용하면 될듯?
//memory 가 m이 되면 현재 result값인 cost가 더 min이면 result 업데이트

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

	cin >> n >> m;

	memory.push_back(0);
	cost.push_back(0);

	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		memory.push_back(a);
	}

	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		cost.push_back(a);
	}

	dp[0] = { {0,0} };

	//dp에는 memory 값을 넣어야함 그리고 같이 cost값도 저장해야함 그러면 pair vector를 사용해보자

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			//이전 memoery 값과 현재 memory 값을 더한게 m값보다 작을때 -> 메모리 최적화가 가능함
			if (dp[i - 1].front().first + dp[i].front().first <= m) {
				
 				dp[i].front().first = dp[i - 1].front().first + dp[i].front().first;

				//코스트 더하기
				dp[i].front().second = dp[i - 1].front().second + dp[i].front().second;
			}
		}
		if (dp[i].front().first == m) {
			result = min(result, dp[i].front().second);
		}
	}

	cout << result << "\n";

	return 0;
}